排序

• 1: 内部排序
• 2: 外部排序

# 排序

## 排序的基本概念

## 内部排序

- 直接插入排序
- 折半插入排序
- 冒泡排序
- 简单选择排序
- 希尔排序
- 快速排序
- 堆排序
- 二路归并排序
- 基数排序

## 外部排序

## 排序算法的分析

1 - 内部排序

排序概念

稳定性

排序算法的 稳定性 是指：在排序过程中，如果两个元素的键值相等，排序后它们的 相对顺序保持不变，那么这个排序算法就是 稳定的排序算法。

比如排序前的数组是这样：[... A ... B ...]，并且 A 和 B 的值相同。

如果排序后的数组是这样：[... B A ...]，那么排序算法就是不稳定的，反之排序算法就是 稳定的。

元素移动次数

排序算法中的 元素移动次数，指的是在排序过程中对 数组元素进行位置变换的次数。

下表列出了各排序算法的 元素移动次数：

可以观察到，选择排序 和 桶排序 的 元素移动次数 是最少的，不涉及到大量的元素位置交换。

复杂度

趟特征

在排序算法中，一趟（pass） 通常指 完成一次从头到尾（或部分范围）对数组进行处理的过程，这一过程中可能会比较、移动、插入或交换若干元素。
换句话说，一趟就是排序算法中最小的完整“循环工作单元”，通常对应于外层循环的一次执行。

不同的排序算法在每趟排序后，数组中的元素会呈现不同特征，总结为下表：

伪代码

• 冒泡排序
• 插入排序
• 选择排序
• 基数排序
• 归并排序
• 希尔排序
• 快速排序
• 堆排序

BubbleSort(arr)
    n ← arr.length
    for i from 0 to n - 1
        for j from 0 to n - i - 2
            if arr[j] > arr[j + 1]
                swap arr[j], arr[j + 1]

InsertionSort(arr)
    n ← arr.length
    for i from 1 to n - 1
        key ← arr[i]
        j ← i - 1
        while j ≥ 0 and arr[j] > key
            arr[j + 1] ← arr[j]
            j ← j - 1
        arr[j + 1] ← key

SelectionSort(arr)
    n ← arr.length
    for i from 0 to n - 1
        minIndex ← i
        for j from i + 1 to n - 1
            if arr[j] < arr[minIndex]
                minIndex ← j
        swap arr[i], arr[minIndex]

RadixSort(arr)
    找到数组中最大值，确定最大位数 d
    for i from 1 to d
        对数组按第 i 位进行**稳定排序**

MergeSort(arr)
    if arr.length ≤ 1
        return arr
    mid ← arr.length / 2
    left ← MergeSort(arr[0 to mid - 1])
    right ← MergeSort(arr[mid to end])
    return Merge(left, right)

Merge(left, right)
    result ← []
    while left ≠ ∅ and right ≠ ∅
        if left[0] ≤ right[0]
            append left[0] to result
            remove left[0] from left
        else
            append right[0] to result
            remove right[0] from right
    append remaining elements of left and right to result
    return result

ShellSort(arr)
    n ← arr.length
    gap ← n / 2
    while gap > 0
        for i from gap to n - 1
            temp ← arr[i]
            j ← i
            while j ≥ gap and arr[j - gap] > temp
                arr[j] ← arr[j - gap]
                j ← j - gap
            arr[j] ← temp
        gap ← gap / 2

QuickSort(arr, low, high)
    if low < high
        pivotIndex ← Partition(arr, low, high)
        QuickSort(arr, low, pivotIndex - 1)
        QuickSort(arr, pivotIndex + 1, high)

Partition(arr, low, high)
    pivot ← arr[high]
    i ← low - 1
    for j from low to high - 1
        if arr[j] ≤ pivot
            i ← i + 1
            swap arr[i], arr[j]
    swap arr[i + 1], arr[high]
    return i + 1

HeapSort(arr)
    BuildMaxHeap(arr)
    for i from arr.length - 1 down to 1
        swap arr[0], arr[i]
        MaxHeapify(arr, 0, i)

BuildMaxHeap(arr)
    n ← arr.length
    for i from n / 2 - 1 down to 0
        MaxHeapify(arr, i, n)

MaxHeapify(arr, i, n)
    largest ← i
    left ← 2 * i + 1
    right ← 2 * i + 2
    if left < n and arr[left] > arr[largest]
        largest ← left
    if right < n and arr[right] > arr[largest]
        largest ← right
    if largest ≠ i
        swap arr[i], arr[largest]
        MaxHeapify(arr, largest, n)

冒泡排序

冒泡排序（Bubble Sort）是一种 简单的排序算法，通过反复遍历数组，比较相邻元素并交换位置，将较大的（或较小的）元素逐步“冒泡”到数组的一端。过程如下：

1. 从数组开头开始，比较相邻的两个元素，如果顺序不对（例如前者大于后者，假设升序排序），则交换它们。
2. 遍历一遍后，最大（或最小）的元素会被“冒泡”到数组末尾（或开头）。
3. 对剩余的未排序部分重复上述步骤，每次遍历的范围减少一个元素，直到数组完全排序。

在升序排序中，较大的元素像气泡一样逐渐“浮”到数组的末端（或较小的元素“沉”到开头），每次遍历都将一个元素推到正确的位置，形似气泡在水中上升的过程，因此得名 “冒泡排序”。

比如，对于数组 5, 1, 4, 2, 8的前两次冒泡过程如下：

插入排序

插入排序（Insertion Sort）将数组分为 未排序部分 和 已排序部分，每次选取未排序部分的第一个元素作为插入元素，在已排序序列中 从后向前 扫描，找到相应位置并插入。

对于数组 4, 3, 2, 10, 12, 1, 5, 6 执行插入排序的过程：

插入排序可以分为 直接插入排序 和 折半插入排序 ，其不同点在于 寻找插入位置时 使用的是 从后向前顺序查找 还是 折半查找。

插入排序适合 大部分元素有序 的场景，因为这种情况下进行插入比较的次数较少，排序算法执行更加高效。

例如，对于序列 1, 2, 3, 5, 4, 6, 7, 8，只有元素 4 的位置不正确，插入排序仅需将 4 向前移动一个位置即可完成排序。而对于 8, 7, 6, 5, 4, 3, 2, 1 这样的逆序序列，每个元素都需要移动到已排序部分的开头，需要进行大量比较和移动，因此效率最低。

因此，插入排序的时间复杂度与序列的 初始有序程度 密切相关：

• 最好情况：序列已经有序，每个元素只需比较一次即可，时间复杂度为 $O(n)$ ；
• 最坏情况：序列完全逆序，每个元素都需要移动到最前面，时间复杂度为 $O(n^2)$ ；
• 平均情况：时间复杂度为 $O(n^2)$ 。

选择排序

选择排序（Selection Sort）将待排序序列划分为 已排序部分 和 未排序部分。每一趟排序都 从未排序部分中选出关键字最小（或最大）的元素，并与未排序部分的第一个元素交换，使其进入已排序部分。

经过第 i 趟排序后，前 i+1 个元素均已处于最终位置，因此未排序部分不断缩小，已排序部分不断扩大，直到整个序列有序。

以排序数组 11, 25, 12, 22, 64 为例：

归并排序

归并排序（Merge Sort）是一种典型的 分而治之（Divide and Conquer） 排序算法。它将待排序序列不断划分为规模更小的子序列，分别排序后，再将多个有序子序列逐步合并，最终得到一个完全有序的序列。

归并排序的核心操作称为 二路归并（Two-way Merge），即 将两个已经有序的序列合并成一个更大的有序序列。归并时，同时从两个有序序列的首元素开始比较，每次取出较小（或较大）的元素放入结果序列，直到两个序列全部合并完成。例如：

• 1, 4, 7 和 2, 3, 8 ⟶ 二路归并后得到 1, 2, 3, 4, 7, 8

上图展示了二路归并的一次典型比较过程：

• 指针 i、j 分别指向序列 A 和序列 B 的当前待比较元素（此时是 1 和 2）；
• 两者进入"比较"环节，取较小的一个（1）放入结果序列；
• 指针 i 后移一位，继续与 j 指向的元素比较，如此重复；
• 图中结果序列的前两格（1、2）已经填入，后面的虚线格子表示尚未归并的位置。

归并排序实际上就是不断重复 “分解 → 二路归并” 的过程：先将长度为 1 的有序子序列两两归并，再归并长度为 2 的有序子序列，接着归并长度为 4 的有序子序列……直到整个序列合并完成。

归并排序的流程可以总结为如下步骤：

1. 分解（Divide）：将待排序序列不断二分，直到每个子序列只包含一个元素（单个元素天然有序）。
2. 递归（Conquer）：递归地对子序列执行相同的操作。
3. 归并（Merge）：采用二路归并的方法，将两个相邻的有序子序列合并成一个更大的有序序列，直到整个序列有序。

快速排序

快速排序（Quick Sort）的核心思想与 归并排序 类似，同样采用 分治法（Divide and Conquer），但两者的实现方式有所不同。

归并排序是 先递归划分，再合并；而快速排序则是 先分区，再递归。每次都会选择一个 基准元素（Pivot），将数组划分为左右两个部分，然后分别对左右子数组继续排序。

快速排序的基本步骤如下：

1. 选择基准元素（Pivot）：从当前区间中选择一个元素作为基准。
2. 分区（Partition）：重新排列数组，使所有小于基准的元素位于左侧，所有大于基准的元素位于右侧。分区结束后，基准元素已经处于最终排序位置。
3. 递归排序子数组：分别对基准左侧和右侧的子数组继续执行快速排序，直到区间长度为 1 或 0。

流程

快速排序通常由两个函数组成：

• partition：完成一次分区操作，并返回基准元素最终所在的位置；
• quickSort：递归调用 partition，分别排序左右两个子数组。

下面采用 双指针法 实现 partition，代码较为简洁，也是考研中最常见的实现方式。

// [low, high] 为分区的范围，返回值为分区后 pivot 在数组中的下标
int partition(int a[], int low, int high) {
    int pivot = a[low];     // 选择区间第一个元素作为基准
    int l = low, r = high;

    while (l < r) {
        while (l < r && a[r] >= pivot) r--; // 从右向左寻找小于 pivot 的元素
        while (l < r && a[l] <= pivot) l++; // 从左向右寻找大于 pivot 的元素
        if (l < r) swap(a[l], a[r]);        // 交换两个元素
    }

    swap(a[low], a[r]); // 将 pivot 放到最终位置
    return r;
}

void quickSort(int a[], int low, int high) {
    // 递归结束条件
    if (low < high) {
        int pivotIdx = partition(a, low, high);

        quickSort(a, low, pivotIdx - 1);
        quickSort(a, pivotIdx + 1, high);
    }
}

快速排序的代码实现需要熟练掌握（能够手写代码），作为算法设计题的兜底方案。

分区

下图以数组 [5, 3, 8, 1, 9, 4, 7, 2] 为例，展示 partition 中 l、r 和 pivot 的移动及交换过程。

经过一次分区后，可以得到如下结论：

• 基准元素左侧的元素都 不大于 基准；
• 基准元素右侧的元素都 不小于 基准；
• 基准元素已经位于最终排序位置，之后不会再移动。

双向递归

一次分区完成后，基准元素已经位于最终排序位置，数组被划分为两个互不重叠的子数组：

• 左子数组：所有元素都 不大于 基准元素；
• 右子数组：所有元素都 不小于 基准元素。

此时，左右两个子数组内部仍然可能是无序的，因此需要分别对它们继续执行快速排序，即对两个子数组分别递归调用 quickSort。

随着递归不断进行，每个子数组都会继续被划分为更小的子数组。当子数组中 元素个数小于等于 1（即 low >= high）时，该子数组已经天然有序，此时递归结束，不再继续划分。

单向递归算法

快速排序每完成一次分区，都会确定 一个基准元素 的最终位置，因此如果我们并不需要整个数组有序，而只是希望找到某一个特定位置的元素，就没有必要继续递归两个方向。

例如，在寻找数组中 第 k 小（或第 k 大）元素 时：

• 如果基准元素正好位于目标位置，则直接返回；
• 如果目标位置位于左半部分，只需递归左侧；
• 如果目标位置位于右半部分，只需递归右侧。

这种算法称为 Quick Select（快速选择），其思想与快速排序完全相同，只是每次分区后 只递归一个子区间，因此也称为 单向递归算法。

// 分区算法与快速排序相同，这里不再赘述
int partition(int a[], int low, int high) { ... }

// 查找有序数组中下标为 k（从 0 开始）的元素
int quickSelect(int a[], int low, int high, int k) {
    if (low < high) {
        int pivotIdx = partition(a, low, high);

        // 找到目标元素
        if (pivotIdx == k) {
            return a[pivotIdx];
        }

        // 目标位于右半部分
        if (pivotIdx < k) {
            return quickSelect(a, pivotIdx + 1, high, k);
        }

        // 目标位于左半部分
        return quickSelect(a, low, pivotIdx - 1, k);
    }

    return a[low];
}

注意

上述代码中的 k 表示 有序数组中的下标（从 0 开始）。若题目要求寻找 第 k 大元素，通常需要先转换为对应的数组下标，再调用 quickSelect。

堆排序

堆排序的核心在于利用 堆的性质 进行排序，在了解堆排序过程之前，需要了解堆的基本概念。

堆

在二叉树一节中我们提到，二叉树的存储方式 包含 链接存储 和 顺序存储 两种。
堆就是采用 顺序存储 的方式，在这种方式中，我们使用一个数组来模拟一颗二叉树，二叉树中的结点操作被转化为数组元素操作。

满足以下性质的树 被称为 堆（Heap）：

1. 结构性质：堆总是一颗 完全二叉树，即除了最后一层之外的其他每一层都被元素填满，且最后一层的元素都尽可能地靠左排列。
2. 有序性质：树中的每个结点 相对于 子结点 都保证有序关系，要么父结点的值都 大于等于 子结点的值，要么都 小于等于 子结点的值，按照这种有序关系堆可以分为两种类型：
   • 大根堆 （Max Heap）：堆中的任意结点，其值都 ≥ 其子结点的值。这意味着 根结点是最大值。
   • 小根堆 （Min Heap）：堆中的任意结点，其值都 ≤ 其子结点的值。这意味着 根结点是最小值。

基于这些性质，堆常常被用于实现 优先队列。对于大根堆，我们总是可以在 O(1) 的时间内得到最大的元素（即根结点），而对于小根堆，我们总是可以在 O(1) 的时间内得到最小的元素。

实现

堆通常使用数组来实现，而不需要使用真正的树或链表结构。利用数组实现堆时，每个元素都有一个固定的位置，而该位置与元素在树中的位置有关。

假设数组的起始索引为 1，若某元素的索引为 i，则它的：

• 左孩子的索引为 2i
• 右孩子的索引为 2i + 1
• 父结点的索引为 i/2 （整数除法）

如果数组的起始索引为 0，若某元素的索引为 i，则它的：

• 左孩子的索引为 2i + 1
• 右孩子的索引为 2i + 2
• 父结点的索引为 (i-1)/2（整数除法）

操作

对于堆，重点掌握 堆化（heapify）、构建初始堆、删除 和 插入 操作。

堆化是从某个结点开始，调整以该结点为根的子树，使其满足堆性质（以最大堆为例说明其过程）：

• 比较 当前结点 与 左右子结点 的值。
• 如果某个子结点 比当前结点大，交换当前结点与较大的子结点。
• 交换后，继续对 被交换的子结点 递归地执行堆化，直到子树满足堆性质。

以大根堆 50,13,40,30,20,22,24,15,11 为例，若我们从结点 13 执行堆化，会发生如下图所示的过程：

注意堆化的过程是递归的，当我们交换父结点和子结点后，需要从子结点进一步执行堆化操作。

构造初始堆有两种方式：

• 方法 1：向一个初始为空的堆中不断 插入 新的元素。
• 方法 2：将无序数组转化为最大堆，核心是从 最后一个非叶子结点 开始，从后向前逐一对每个子树执行 堆化 操作。

以数组 1,3,5,4,6,13,10,9,8,15,17 为例，假设我们使用方法 2 将其初始化为大根堆，会发生如下图所示的过程：

堆中的删除一般都发生在 堆顶，其过程如下：

• 将堆顶元素和堆中最后一个元素互换，然后删除最后一个结点
• 对新的堆顶执行 堆化，调整堆使其重新满足最大堆性质

在堆中插入新元素后，需维护堆性质。

• 将新元素添加到堆底（数组末尾）。
• 从新元素开始，向上与父结点比较，若 大于父结点 则交换（上浮）。
• 重复上浮直到满足堆性质或到达堆顶。

• 堆化
• 构造初始堆
• 堆插入元素
• 堆删除元素

// 调整 i 结点为根的子树，使其满足堆的性质
void heapify(int heap[], int size, int i) {
    int largest = i;       // 假设当前结点是最大的
    int left = 2 * i + 1;  // 左结点下标
    int right = 2 * i + 2; // 右结点下标
    if (left < size && heap[left] > heap[largest]) {
        largest = left;
    }
    if (right < size && heap[right] > heap[largest]) {
        largest = right;
    }
    // 如果最大值不是根结点
    if (largest != i) {
        swap(heap[i], heap[largest]);
        heapify(heap, size, largest);  // 递归堆化受影响的子树
    }
}