CS61B 课程笔记（Lecture 32 Basic Sorting Algorithms)

排序问题

排序问题可以被非正式地定义为将一组给定的项目按特定顺序排列。排序不仅在自身有用，也可以作为更大算法问题的子问题。排序可以应用于查找重复项（排序后，相同的项相邻）、二分搜索和数据结构平衡等问题。

排序提供了处理计算问题的一般思路。解决排序问题的过程通常会涉及到之前部分讨论过的数据结构。

排序的定义

一个关于键 ( \(a, b, c\) ) 的顺序关系 ($ < $) 具有以下属性：

1. 三分律（\(Law of Trichotomy\)）：对于任意两个元素 ($ a$ ) 和 ( $b $)，以下三者中恰好有一个为真：( \(a < b\) )、( \(a = b\) )、( \(b < a\) )。
2. 传递性（\(Law of Transitivity\)）：如果 ( \(a < b\) ) 且 ( \(b < c\) )，则 ($ a < c$ )。

具有上述属性的排序关系称为全序（\(Total Order\)）。

一个排序是对一组元素的一个排列，使得键按照给定的顺序关系按非递减顺序排列，即 ( $x_1 x_2 x_3 ... x_N $)。

示例：字符串长度

使用字符串长度作为排序关系的例子：

• 三分律：对于两个字符串 ( \(a\) ) 和 ($ b$ )，只有以下三种情况之一可以为真：($ (a) < (b) $)、( \(\text{len}(a) = \text{len}(b)\) )、或 ( \(\text{len}(a) > \text{len}(b)\) )。
• 传递性：如果 ( $(a) < (b) $) 且 ( $(b) < (c) \(\)，那么 \(\) (a) < (c) $)。

例如，对于数组 ["cows", "get", "going", "the"]，有效的排序可以是 ["the", "get", "cows", "going"] 或 ["get", "the", "cows", "going"]。

Java中的排序关系

在Java中，排序关系通常通过 compareTo 或 compare 方法来定义。例如：

import java.util.Comparator;

public class LengthComparator implements Comparator<String> {
    public int compare(String x, String b) {
        return x.length() - b.length();
    }
}

在这个例子中，"the" 和 "get" 在排序中是相等的，但不相等于 .equals() 方法。

逆序对

另一种看待排序的方法是修复序列中的逆序。逆序是指相对于定义的顺序关系而错位的一对元素。例如，在11个元素的序列中，最多有55个逆序（11选2），而该序列实际有6个逆序。

排序可以被视为：给定一个有 ( Z ) 个逆序的元素序列，通过某些操作将逆序总数减少到零。

排序算法的性能

排序算法的运行时效率称为时间复杂度。例如，Dijkstra算法的时间复杂度为 ($ O(E V)$ )。

算法的额外内存使用称为空间复杂度。例如，Dijkstra的空间复杂度为 ($ (V) $)，用于存储队列、distTo 和 edgeTo 数组。

选择排序（Selection Sort）

选择排序的算法步骤如下：

1. 找到最小的元素。
2. 将该元素交换到前面。
3. 重复以上步骤，直到所有元素固定（没有逆序）。

选择排序的时间复杂度为 ( \(\Theta(N^2)\) )，在使用数组或类似数据结构时，效率较低，因为每次都需要遍历剩余数组寻找最小值。

堆排序（Heapsort）

基本堆排序（Naive Heapsort）

为了避免选择排序中的低效，我们可以利用最大堆（max-heap）来改进：

1. 将所有元素插入最大堆中，创建输出数组。
2. 重复删除最大堆中的最大元素，并将其放在输出数组的末尾。

基本堆排序的整体运行时间为 ( $(N N) $)，主要包含三个部分：

• 将 ( \(N\) ) 个元素插入堆：( \(O(N \log N)\) )
• 选择最大元素：($ (1) $)
• 移除最大元素：( \(O(\log N)\) )

原地堆排序（In-place Heapsort）

我们可以使用输入数组本身来形成堆和输出数组。通过反向层序遍历的底部堆化（bottom-up heapification）过程，可以将输入数组转化为堆。堆化后，重复弹出最大元素并放置到数组末尾。

• 原地堆排序的时间复杂度仍为 ( \(O(N \log N)\))。
• 使用原地堆排序时，内存使用降至 ( \(\Theta(1)\) )，因为我们复用了输入数组。

合并排序（Mergesort）

合并排序的算法步骤如下：

1. 将元素分为两半。
2. 对每一半递归调用合并排序。
3. 合并两个已排序的部分，形成最终结果。

合并排序的运行时间为 ($ (N N)$ )，在合并步骤中需要 ($ (N) $) 的额外空间。

插入排序（Insertion Sort）

朴素插入排序

在插入排序中，我们从输入中选择元素，将其插入到正确的位置。朴素方法是创建一个单独的输出数组，将输入中的元素放入。

原地插入排序（In-place Insertion Sort）

通过使用原地交换而不是创建新的输出数组，可以提高插入排序的时间和空间复杂度。原地插入排序的算法如下：

1. 从左到右遍历数组。
2. 选择每个元素，并将其交换到前面尽可能远的位置。

插入排序的运行时间：

• 最好情况下：( $(N) $)（没有交换）。
• 最坏情况下：( \(\Theta(N^2)\) )（逆序数组）。

插入排序的优点：在已排序或几乎已排序的数组上，插入排序的工作量很少。

总结

• 逆序：序列中的逆序对数目。
• 选择排序：通过选择极值并将其移动到未排序部分末尾。
• 堆排序：利用堆数据结构进行排序，相较于选择排序大幅提高效率。
• 合并排序：分而治之的方法，较复杂但效率较高。
• 插入排序：对于小规模或几乎排序的数组非常高效。

以下是选择排序、堆排序、合并排序和插入排序的Java代码实现

选择排序（Selection Sort）

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            // 找到未排序部分的最小元素
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // 更新最小元素索引
                }
            }
            // 交换最小元素与当前元素
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组: " + java.util.Arrays.toString(arr));
    }
}

堆排序（Heapsort）

基本堆排序（Naive Heapsort）

import java.util.Arrays;

public class NaiveHeapsort {
    public static void heapsort(int[] arr) {
        int n = arr.length;
        // 建立最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // 逐个移除最大元素
        for (int i = n - 1; i > 0; i--) {
            // 交换当前根节点（最大元素）与最后一个元素
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // 重新堆化
            heapify(arr, i, 0);
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        int largest = i; // 初始化最大的元素为根
        int left = 2 * i + 1; // 左子节点
        int right = 2 * i + 2; // 右子节点
        // 如果左子节点大于根节点
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        // 如果右子节点大于目前最大节点
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // 如果最大节点不是根节点
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            // 递归堆化影响到的子树
            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        heapsort(arr);
        System.out.println("排序后的数组: " + Arrays.toString(arr));
    }
}

原地堆排序（In-place Heapsort）

import java.util.Arrays;

public class InPlaceHeapsort {
    public static void inPlaceHeapsort(int[] arr) {
        int n = arr.length;
        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // 从堆中逐个提取元素
        for (int i = n - 1; i > 0; i--) {
            // 交换当前最大值（根）与最后一个元素
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // 重新调整堆
            heapify(arr, i, 0);
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 6, 8, 10, 1, 2, 1};
        inPlaceHeapsort(arr);
        System.out.println("排序后的数组: " + Arrays.toString(arr));
    }
}

合并排序（Mergesort）

import java.util.Arrays;

public class Mergesort {
    public static void mergesort(int[] arr) {
        if (arr.length < 2) {
            return; // 只有一个元素时不需要排序
        }
        int mid = arr.length / 2;
        // 分割数组
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        mergesort(left); // 递归排序左半部分
        mergesort(right); // 递归排序右半部分
        merge(arr, left, right); // 合并已排序的部分
    }

    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        // 合并两个已排序的数组
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }
        // 复制剩余的元素
        while (i < left.length) {
            arr[k++] = left[i++];
        }
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergesort(arr);
        System.out.println("排序后的数组: " + Arrays.toString(arr));
    }
}

插入排序（Insertion Sort）

朴素插入排序

import java.util.Arrays;

public class NaiveInsertionSort {
    public static void naiveInsertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // 将大于key的元素移动到前面
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key; // 插入到正确位置
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        naiveInsertionSort(arr);
        System.out.println("排序后的数组: " + Arrays.toString(arr));
    }
}

原地插入排序（In-place Insertion Sort）

import java.util.Arrays;

public class InPlaceInsertionSort {
    public static void inPlaceInsertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // 将大于key的元素移动到前面
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key; // 插入到正确位置
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5, 6};
        inPlaceInsertionSort(arr);
        System.out.println("排序后的数组: " + Arrays.toString(arr));
    }
}