排序算法 (Sorting Algorithms)

1. 引言

1.1 排序的定义与重要性

排序（Sorting）是将一组数据元素按照特定顺序（通常是数字顺序或字典顺序）重新排列的过程。

• 输入：$n$ 个数的序列 $⟨a_1,a_2,\dots ,a_n⟩$。
• 输出：原序列的一个重排 $⟨a_1^{\prime },a_2^{\prime },\dots ,a_n^{\prime }⟩$，满足 $a_1^{\prime }\le a_2^{\prime }\le \cdots \le a_n^{\prime }$。 排序是计算机科学中最基本的操作之一，广泛用于数据库优化、二分查找预处理、数据压缩和图形渲染等领域。

1.2 排序算法的分类

• 比较排序 vs 非比较排序：前者通过元素间的比较决定顺序，后者利用数据本身的特性（如计数值）。
• 内部排序 vs 外部排序：前者数据全部加载到内存，后者数据量过大需借助外部存储（磁盘）。
• 递归排序 vs 非递归排序。

1.3 评价标准

1.3.1 时间复杂度

• 最好情况：数据已经有序时。
• 最坏情况：数据完全逆序或特定排列时。
• 平均情况：随机数据的期望运行时间。
• 通常关注渐进上界 $O(n^2)$ 或 $O(n\log n)$。

1.3.2 空间复杂度

算法执行过程中所需的额外内存空间。理想情况是 $O(1)$。

1.3.3 稳定性 (Stability)

如果两个相等的元素 $A$ 和 $B$ 在排序前的序列中 $A$ 在 $B$ 前面，排序后 $A$ 依然在 $B$ 前面，则称算法是稳定的。这在多关键字排序（如先按分数排，再按名字排）中非常重要。

1.3.4 原地排序 (In-place)

除了输出数组外，只需要常数阶 $O(1)$ 的额外空间。

2. 简单排序算法

2.1 冒泡排序（Bubble Sort）

2.1.1 算法原理

重复遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

2.1.2 算法实现

void bubbleSort(int nums[], int size) {
    // 外循环：未排序区间为 [0, i]
    for (int i = size - 1; i > 0; i--) {
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

2.1.3 复杂度分析

• 时间：平均 $O(n^2)$，最坏 $O(n^2)$，最好 $O(n)$。
• 空间：$O(1)$。
• 稳定性：稳定。

2.1.4 优化方案

设置标志位 swapped，如果一轮遍历中没有交换，直接结束；记录最后一次交换的位置，减少遍历范围（鸡尾酒排序是其变种）。

2.2 选择排序（Selection Sort）

2.2.1 算法原理

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置。

2.2.2 算法实现

void selectionSort(int nums[], int n) {
    // 外循环：未排序区间为 [i, n-1]
    for (int i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k])
                k = j; // 记录最小元素的索引
        }
        // 将该最小元素与未排序区间的首个元素交换
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
    }
}

2.2.3 复杂度分析

• 时间：无论数据状况如何，均为 $O(n^2)$。
• 空间：$O(1)$。
• 稳定性：不稳定（例如序列 [5, 5, 2]，交换第一个 5 和 2 会破坏两个 5 的相对顺序）。

2.3 插入排序（Insertion Sort）

2.3.1 算法原理

构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。类似于打扑克牌整理手牌。

2.3.2 算法实现

/* 插入排序 */
void insertionSort(int nums[], int size) {
    // 外循环：已排序区间为 [0, i-1]
    for (int i = 1; i < size; i++) {
        int base = nums[i], j = i - 1;
        // 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
        while (j >= 0 && nums[j] > base) {
            // 将 nums[j] 向右移动一位
            nums[j + 1] = nums[j];
            j--;
        }
        // 将 base 赋值到正确位置
        nums[j + 1] = base;
    }
}

2.3.3 复杂度分析

• 时间：平均 $O(n^2)$，最坏 $O(n^2)$，最好 $O(n)$（接近有序时效率极高）。
• 空间：$O(1)$。
• 稳定性：稳定。

2.3.4 二分插入排序

在查找插入位置时使用二分查找，将比较次数减少到 $O(n\log n)$，但移动次数仍为 $O(n^2)$。

2.4 希尔排序（Shell Sort）

2.4.1 算法原理

插入排序的改进版（缩小增量排序）。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

2.4.2 算法实现

关键在于增量序列（Gap Sequence）的选择（如 n/2, n/4... 或 Knuth 序列 3k+1）。

2.4.3 复杂度分析

• 时间：取决于增量序列，平均可达 $O(n^{1.3})$ 或 $O(n{\log }^{2}n)$。突破了 $O(n^2)$ 的限制。
• 稳定性：不稳定。

3. 高效排序算法

3.1 归并排序（Merge Sort）

3.1.1 分治思想

将数组分成两半，分别对它们进行排序，然后将两个有序数组合并成一个有序数组。

3.1.2 算法实现

• 分解：$O(1)$。
• 解决：递归调用。
• 合并：$O(n)$。

/* 合并左子数组和右子数组 */
void merge(int *nums, int left, int mid, int right) {
    // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
    // 创建一个临时数组 tmp ，用于存放合并后的结果
    int tmpSize = right - left + 1;
    int *tmp = (int *)malloc(tmpSize * sizeof(int));
    // 初始化左子数组和右子数组的起始索引
    int i = left, j = mid + 1, k = 0;
    // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }
    // 将左子数组和右子数组的剩余元素复制到临时数组中
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
    for (k = 0; k < tmpSize; ++k) {
        nums[left + k] = tmp[k];
    }
    // 释放内存
    free(tmp);
}

/* 归并排序 */
void mergeSort(int *nums, int left, int right) {
    // 终止条件
    if (left >= right)
        return; // 当子数组长度为 1 时终止递归
    // 划分阶段
    int mid = left + (right - left) / 2;    // 计算中点
    mergeSort(nums, left, mid);      // 递归左子数组
    mergeSort(nums, mid + 1, right); // 递归右子数组
    // 合并阶段
    merge(nums, left, mid, right);
}

3.1.3 复杂度分析

• 时间：严格的 $O(n\log n)$。
• 空间：$O(n)$（需要辅助数组），这是其主要缺点。
• 稳定性：稳定。

3.1.4 空间优化

可以使用原地归并（实现极其复杂且常数大）或在数组规模较小时切换为插入排序。

3.2 快速排序（Quick Sort）

3.2.1 分治思想

通过一个“基准”（Pivot）将数组分为两部分：比基准小的放在左边，比基准大的放在右边。然后递归排序。

3.2.2 分区操作 (Partition)

• Lomuto 分区：单向扫描，实现简单。
• Hoare 分区：双向扫描，效率略高，交换次数少。

3.2.3 算法实现

/* 元素交换 */
void swap(int nums[], int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

/* 哨兵划分 */
int partition(int nums[], int left, int right) {
    // 以 nums[left] 为基准数
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) {
            j--; // 从右向左找首个小于基准数的元素
        }
        while (i < j && nums[i] <= nums[left]) {
            i++; // 从左向右找首个大于基准数的元素
        }
        // 交换这两个元素
        swap(nums, i, j);
    }
    // 将基准数交换至两子数组的分界线
    swap(nums, i, left);
    // 返回基准数的索引
    return i;
}

3.2.4 复杂度分析

• 时间：平均 $O(n\log n)$，最坏 $O(n^2)$（当数据有序且每次选第一个为基准时）。
• 空间：$O(\log n)$（递归栈空间）。
• 稳定性：不稳定。

3.2.5 随机化快排

每次随机选取 Pivot，可以从概率上避免最坏情况的发生。

3.2.6 三路快排 (3-Way Quick Sort)

将数组分为三部分：< Pivot、= Pivot、> Pivot。对包含大量重复元素的数组非常高效，复杂度降为 $O(n)$。

3.3 堆排序（Heap Sort）

3.3.1 堆的概念

利用堆（Heap）这种数据结构。通常使用大顶堆（Max-Heap），堆顶为最大元素。

3.3.2 堆的构建

• Heapify：调整节点使其满足堆性质。
• Build-Heap：从最后一个非叶子节点开始向上调整，时间 $O(n)$。

3.3.3 算法实现

1. 构建大顶堆。
2. 将堆顶元素与末尾元素交换。
3. 堆尺寸减 1，对新的堆顶进行 Heapify。
4. 重复直到堆尺寸为 1。

/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
void siftDown(int nums[], int n, int i) {
    while (1) {
        // 判断节点 i, l, r 中值最大的节点，记为 ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma == i) {
            break;
        }
        // 交换两节点
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // 循环向下堆化
        i = ma;
    }
}

/* 堆排序 */
void heapSort(int nums[], int n) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (int i = n / 2 - 1; i >= 0; --i) {
        siftDown(nums, n, i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (int i = n - 1; i > 0; --i) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums, i, 0);
    }
}

3.3.4 复杂度分析

• 时间：严格的 $O(n\log n)$。
• 空间：$O(1)$。
• 稳定性：不稳定。

4. 特殊排序算法（线性时间排序）

4.1 计数排序（Counting Sort）

4.1.1 算法原理

统计每个整数在序列中出现的次数，进而推导出每个数字在有序序列中的索引。

4.1.2 算法实现

需要一个大小为 $k$ （数据范围）的辅助数组 counter。

/* 计数排序 */
// 简单实现，无法用于排序对象
void countingSortNaive(int nums[], int size) {
    // 1. 统计数组最大元素 m
    int m = 0;
    for (int i = 0; i < size; i++) {
        if (nums[i] > m) {
            m = nums[i];
        }
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    int *counter = calloc(m + 1, sizeof(int));
    for (int i = 0; i < size; i++) {
        counter[nums[i]]++;
    }
    // 3. 遍历 counter ，将各元素填入原数组 nums
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
    // 4. 释放内存
    free(counter);
}

4.1.3 适用场景

适用于量大但范围小（$k$ 较小）的整数排序。

4.1.4 复杂度分析

• 时间：$O(n+k)$。
• 空间：$O(k)$。
• 稳定性：稳定。

4.2 基数排序（Radix Sort）

4.2.1 算法原理

将整数按位数切割成不同的数字，然后按每个位数分别比较。

4.2.2 LSD 与 MSD

• LSD (Least Significant Digit)：从低位到高位排序。
• MSD (Most Significant Digit)：从高位到低位排序（需递归）。

4.2.3 算法实现

通常每一位的排序使用计数排序作为子过程。

/* 获取元素 num 的第 k 位，其中 exp = 10^(k-1) */
int digit(int num, int exp) {
    // 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
    return (num / exp) % 10;
}

/* 计数排序（根据 nums 第 k 位排序） */
void countingSortDigit(int nums[], int size, int exp) {
    // 十进制的位范围为 0~9 ，因此需要长度为 10 的桶数组
    int *counter = (int *)malloc((sizeof(int) * 10));
    memset(counter, 0, sizeof(int) * 10); // 初始化为 0 以支持后续内存释放
    // 统计 0~9 各数字的出现次数
    for (int i = 0; i < size; i++) {
        // 获取 nums[i] 第 k 位，记为 d
        int d = digit(nums[i], exp);
        // 统计数字 d 的出现次数
        counter[d]++;
    }
    // 求前缀和，将“出现个数”转换为“数组索引”
    for (int i = 1; i < 10; i++) {
        counter[i] += counter[i - 1];
    }
    // 倒序遍历，根据桶内统计结果，将各元素填入 res
    int *res = (int *)malloc(sizeof(int) * size);
    for (int i = size - 1; i >= 0; i--) {
        int d = digit(nums[i], exp);
        int j = counter[d] - 1; // 获取 d 在数组中的索引 j
        res[j] = nums[i];       // 将当前元素填入索引 j
        counter[d]--;           // 将 d 的数量减 1
    }
    // 使用结果覆盖原数组 nums
    for (int i = 0; i < size; i++) {
        nums[i] = res[i];
    }
    // 释放内存
    free(res);
    free(counter);
}

/* 基数排序 */
void radixSort(int nums[], int size) {
    // 获取数组的最大元素，用于判断最大位数
    int max = INT32_MIN;
    for (int i = 0; i < size; i++) {
        if (nums[i] > max) {
            max = nums[i];
        }
    }
    // 按照从低位到高位的顺序遍历
    for (int exp = 1; max >= exp; exp *= 10)
        // 对数组元素的第 k 位执行计数排序
        // k = 1 -> exp = 1
        // k = 2 -> exp = 10
        // 即 exp = 10^(k-1)
        countingSortDigit(nums, size, exp);
}

4.2.4 复杂度分析

• 时间：$O(d(n+k))$，其中 $d$ 是最大值的位数。
• 稳定性：稳定。

4.3 桶排序（Bucket Sort）

4.3.1 算法原理

将数据分发到有限数量的桶里。每个桶再分别排序（通常使用插入排序）。

4.3.2 算法实现

映射函数 $f(x)$ 决定放入哪个桶。

/* 桶排序 */
void bucketSort(float nums[], int n) {
    int k = n / 2;                                 // 初始化 k = n/2 个桶
    int *sizes = malloc(k * sizeof(int));          // 记录每个桶的大小
    float **buckets = malloc(k * sizeof(float *)); // 动态数组的数组（桶）
    // 为每个桶预分配足够的空间
    for (int i = 0; i < k; ++i) {
        buckets[i] = (float *)malloc(n * sizeof(float));
        sizes[i] = 0;
    }
    // 1. 将数组元素分配到各个桶中
    for (int i = 0; i < n; ++i) {
        int idx = (int)(nums[i] * k);
        buckets[idx][sizes[idx]++] = nums[i];
    }
    // 2. 对各个桶执行排序
    for (int i = 0; i < k; ++i) {
        qsort(buckets[i], sizes[i], sizeof(float), compare);
    }
    // 3. 合并排序后的桶
    int idx = 0;
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < sizes[i]; ++j) {
            nums[idx++] = buckets[i][j];
        }
        // 释放内存
        free(buckets[i]);
    }
}

4.3.3 复杂度分析

• 时间：如果数据均匀分布，平均 $O(n)$。最坏情况（所有数据进一个桶）退化为桶内排序算法的复杂度。
• 空间：$O(n+k)$。

4.3.4 与其他排序的结合

常用于浮点数排序或外部排序的预处理。

5. 排序算法的理论分析

5.1 比较排序的下界

5.1.1 决策树模型

任何比较排序算法都可以抽象为一棵二叉决策树，叶子节点代表一种可能的排列。

5.1.2 信息论角度

对于 $n$ 个元素，有 $n!$ 种排列。算法必须区分这 $n!$ 种情况。

5.1.3 下界证明

决策树的高度 $h$ 必须满足 $2^h\ge n!$。 根据斯特林公式（Stirling's approximation），$\log (n!)\approx n\log n$。 因此，比较排序的最坏情况时间复杂度下界是 $\mathrm{\Omega }(n\log n)$。

5.2 排序算法的稳定性分析

稳定性不是为了“好看”，而是为了保留之前的排序信息。在基数排序中，稳定是必须的。

5.3 自适应排序与有序性度量

自适应排序（Adaptive Sort）指对于已部分有序的数据，算法能运行得更快（如插入排序）。度量有序性常用“逆序对”数量。

5.4 排序算法的实际性能比较

理论 $O(n\log n)$ 不代表实际最快。快速排序通常最快是因为其内部循环指令极少，且对 CPU 缓存（Cache）友好（局部性原理），而堆排序由于在大数组中跳跃访问，缓存命中率低。

6. 排序算法的应用与变种

6.1 外部排序

6.1.1 多路归并 (Multi-way Merge)

当数据量大于内存时，先分块在内存排序生成“顺串”（Runs），存入磁盘。然后使用 $k$ 路归并算法将顺串合并。

6.1.2 置换选择 (Replacement Selection)

用于在内存受限时生成更长的初始顺串，减少归并趟数。

6.2 字符串排序

6.2.1 三向字符串快排

结合了快速排序和基数排序的特点，特别适合处理有公共前缀的字符串数组。

6.2.2 MSD 字符串排序

从左向右处理字符，适合随机字符串。

6.3 部分排序问题

6.3.1 Top-K 问题

找出最大的 $K$ 个数。可以使用最小堆（$O(n\log K)$）处理。

6.3.2 第 K 小元素

使用快速选择算法（QuickSelect），基于快排的分区思想，平均时间复杂度 $O(n)$。

6.4 动态排序问题

6.4.1 动态排序与数据结构

如果数据源源不断地来，通常使用二叉搜索树（BST）或平衡树（AVL, Red-Black Tree）来维护有序性，插入和查询均为 $O(\log n)$。

7. 实际应用与优化

7.1 混合排序算法 (Hybrid Sorts)

7.1.1 Introsort (内省排序)

• 开始使用快速排序。
• 如果递归深度超过阈值（通常 $2\log n$），切换为堆排序（防止最坏情况）。
• 如果子数组很小，切换为插入排序。

7.1.2 Timsort

• 结合了归并排序和插入排序。
• 利用数据中天然存在的有序片段（Runs）。
• 极其适合现实世界的非随机数据，最坏 $O(n\log n)$，最好 $O(n)$，且稳定。

7.2 并行排序

• 双调排序 (Bitonic Sort)：一种排序网络，非常适合在 GPU 或并行硬件上实现。
• 并行归并：将合并过程并行化。

8. 总结

拉个表格：

类别	算法名称	时间复杂度 (最佳)	时间复杂度 (平均)	时间复杂度 (最差)	空间复杂度 (最差)	稳定性	就地性	自适应性	基于比较
遍历排序 $O(n^2)$	选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	非稳定	原地	非自适应	比较
	冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	原地	自适应	比较
	插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	原地	自适应	比较
分治排序 $O(n\log n)$	快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$	非稳定	原地	非自适应	比较
	归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定	非原地	非自适应	比较
	堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	非稳定	原地	非自适应	比较
线性排序 $O(n)$	桶排序	$O(n+k)$	$O(n+k)$	$O(n^2)$	$O(n+k)$	稳定	非原地	非自适应	非比较
	计数排序	$O(n+m)$	$O(n+m)$	$O(n+m)$	$O(n+m)$	稳定	非原地	非自适应	非比较
	基数排序	$O(nk)$	$O(nk)$	$O(nk)$	$O(n+b)$	稳定	非原地	非自适应	非比较

参数说明：

• $n$：数据量大小
• $k$：桶排序中为桶数量；基数排序中为最大位数
• $m$：计数排序中为数据范围
• $b$：基数排序中为数据进制（数据为 $b$ 进制）

习题

1. [M4.5**] 比较排序算法的下界：

   证明：任何基于比较的排序算法（即仅通过比较元素来确定顺序），在最坏情况下都需要 $\mathrm{\Omega }(n\lg n)$ 次比较来排序 n 个不同的元素。 提示：考虑决策树模型。每个内部节点代表一次比较，叶子节点代表一种可能的排序结果。树的高度对应最坏情况下的比较次数。分析叶子节点的数量和树的高度之间的关系。

2. 探究希尔排序。第 3.5.6. 问查阅资料即可，第 7. 问是截至目前计算机科学界的未解难题。

   (1) [2.1] 希尔排序通过一系列递减的增量（例如，h = {..., 13, 4, 1}）对数组进行多轮“h-排序”。请从概念上解释，为什么这种“分组预排序”的策略，通常会比直接进行一次完整的插入排序（即只有增量为 1）更有效率？

   (2) [M4.4] 考虑希尔本人提出的原始增量序列 h = {..., n/4, n/2, 1}（其中 n 为 2 的幂）。请分析并证明，在使用此序列时，希尔排序的最坏情况时间复杂度为 Θ(n²)。（提示：构造一个最坏情况的数组。例如，数组的前一半填充较大的数，后一半填充较小的数。分析当增量 h > 1 时，元素是否能在数组的两半之间有效移动。）

   为了克服 Θ(n²) 的最坏情况，研究者们提出了许多更优的增量序列。

   (3) [HM7.7**] Hibbard 序列是形如 2^k - 1 的序列 ({..., 15, 7, 3, 1})。证明：它的时间复杂度为 $O(n^{\frac{3}{2}})$。

   (4) [HM7.8**] Knuth 序列是形如 (3^k - 1) / 2 的序列 ({..., 40, 13, 4, 1})。证明：它的时间复杂度为 $O(n^{\frac{3}{2}})$。

   (5) [2.1] Hibbard 序列和 Kunth 序列的时间复杂度相同。哪个更具优越性？

   (6) [HM9.9**] Sedgewick 序列是形如 4^k + 3*2^(k-1) + 1 的序列 ({..., 109, 41, 19, 5, 1})。证明：它的时间复杂度为 $O(n^{\frac{4}{3}})$。

   (7) [HM10.10**] 最好的增量序列是什么？希尔排序的确切的时间复杂度下界是什么？