排序

本节导读

排序是数据结构的最后一章。大纲逐个列了直接插入、折半插入、起泡、简单选择、希尔、快速、堆、二路归并、基数九种内部排序，还有外部排序和「排序算法的分析和应用」。

这一章的选择题多是「某种排序一趟之后的结果」「复杂度与稳定性」「哪种方法合适」；综合应用题可能要写出排序或划分的代码。学完你应该能对任一种方法手算每一趟的结果，背熟复杂度对比表，并写出快速排序的划分函数。

基本概念

排序是把一组记录按关键字排成有序序列。关键字相同的记录排序后相对次序不变，叫稳定的排序，否则不稳定。排序过程中数据全在内存里的叫内部排序，数据太多、要在内外存之间多次交换的叫外部排序。基于比较的内部排序，平均时间复杂度的下界是 $O(n\log_2 n)$O(nlog2​n)。

插入排序

• 直接插入：把第 i 个元素插到前面已排好的 i − 1 个元素中合适的位置，边比较边后移。初始有序时只比较 n − 1 次，最好 $O(n)$O(n)；逆序时最坏 $O(n^2)$O(n2)；稳定。
• 折半插入：用折半查找找插入位置，比较次数降到 $O(n\log_2 n)$O(nlog2​n)，但移动次数不变，总时间仍是 $O(n^2)$O(n2)；稳定。
• 希尔排序：取增量 d，把相隔 d 的元素分成一组各自直接插入排序，再缩小 d，最后 d = 1 做一次直接插入。时间依赖增量序列，常说约为 $O(n^{1.3})$O(n1.3)，最坏 $O(n^2)$O(n2)；不稳定；只能用于顺序表。

交换排序

起泡排序：每趟从前往后比较相邻元素，逆序就交换，一趟把最大的元素「沉」到最后。设交换标志，某趟没有交换就提前结束，所以初始有序时最好 $O(n)$O(n)；稳定。

快速排序：选一个枢轴（下面取第一个元素），一趟划分把比它小的放左边、大的放右边，枢轴落到最终位置，再对两边递归：

int partition(int A[], int low, int high) {
    int pivot = A[low];                  /* 第一个元素作枢轴 */
    while (low < high) {
        while (low < high && A[high] >= pivot) high--;
        A[low] = A[high];                /* 比枢轴小的移到左端 */
        while (low < high && A[low] <= pivot) low++;
        A[high] = A[low];                /* 比枢轴大的移到右端 */
    }
    A[low] = pivot;                      /* 枢轴到达最终位置 */
    return low;
}
void quick_sort(int A[], int low, int high) {
    if (low < high) {
        int p = partition(A, low, high);
        quick_sort(A, low, p - 1);
        quick_sort(A, p + 1, high);
    }
}

每次划分都比较均匀时是 $O(n\log_2 n)$O(nlog2​n)；初始序列有序或逆序时，每次只分出一个元素，退化为 $O(n^2)$O(n2)。递归栈平均深度 $O(\log_2 n)$O(log2​n)，最坏 $O(n)$O(n)。不稳定。

选择排序

简单选择排序：第 i 趟在后 n − i + 1 个元素中选最小的，与第 i 个交换。比较次数总是 $\dfrac{n(n-1)}{2}$2n(n−1)​，与初始序列无关，$O(n^2)$O(n2)；移动次数少；不稳定（交换会跨过相同关键字）。

堆排序：先把序列建成大根堆（第 5 节的筛选法，$O(n)$O(n)）；然后反复把堆顶与当前最后一个元素交换、堆的范围减 1、从根向下调整。共调整 n − 1 次，每次 $O(\log_2 n)$O(log2​n)，总时间 $O(n\log_2 n)$O(nlog2​n)，最好最坏都一样；空间 $O(1)$O(1)；不稳定。

归并排序与基数排序

二路归并排序：把两个相邻的有序子表合并成一个，一趟一趟进行，共 $\lceil \log_2 n \rceil$⌈log2​n⌉ 趟，每趟 $O(n)$O(n)，总时间 $O(n\log_2 n)$O(nlog2​n)，与初始序列无关；合并时要一个与原表同样大的辅助数组，空间 $O(n)$O(n)；稳定。

基数排序不比较关键字：把关键字看成 d 位 r 进制数，最低位优先（LSD）时从个位开始，每趟按这一位「分配」到 r 个队列再按顺序「收集」，共 d 趟。时间 $O(d(n + r))$O(d(n+r))，空间 $O(r)$O(r)；每趟都必须稳定，整个算法稳定。

外部排序

外部排序一般用归并法：先把文件分段读入内存排好，生成 r 个初始归并段；再对归并段做多趟 k 路归并。时间主要花在读写外存上，读写次数与归并趟数 $S = \lceil \log_k r \rceil$S=⌈logk​r⌉ 成正比，所以要么增大 k，要么减少 r。

• 败者树：k 路归并时，每选出一个最小关键字只要 $\lceil \log_2 k \rceil$⌈log2​k⌉ 次比较，不用 k − 1 次，增大 k 也不会让内部比较变多。
• 置换-选择排序：用大小为 w 的工作区边输出边读入，能生成比 w 更长、长度不等的初始归并段（输入随机时平均约 2w），r 因此减少。
• 最优归并树：归并段长度不等时，用 k 叉哈夫曼树安排归并次序，读写次数最少。若 $(r - 1) \bmod (k - 1) = u \ne 0$(r−1)mod(k−1)=u=0，要先补 $k - 1 - u$k−1−u 个长度为 0 的虚段。

排序算法的分析

算法	平均时间	最好	最坏	空间	稳定
直接插入	$O(n^2)$O(n2)	$O(n)$O(n)	$O(n^2)$O(n2)	$O(1)$O(1)	是
折半插入	$O(n^2)$O(n2)	$O(n\log_2 n)$O(nlog2​n)	$O(n^2)$O(n2)	$O(1)$O(1)	是
希尔	依赖增量	—	$O(n^2)$O(n2)	$O(1)$O(1)	否
起泡	$O(n^2)$O(n2)	$O(n)$O(n)	$O(n^2)$O(n2)	$O(1)$O(1)	是
快速	$O(n\log_2 n)$O(nlog2​n)	$O(n\log_2 n)$O(nlog2​n)	$O(n^2)$O(n2)	$O(\log_2 n)$O(log2​n)	否
简单选择	$O(n^2)$O(n2)	$O(n^2)$O(n2)	$O(n^2)$O(n2)	$O(1)$O(1)	否
堆	$O(n\log_2 n)$O(nlog2​n)	$O(n\log_2 n)$O(nlog2​n)	$O(n\log_2 n)$O(nlog2​n)	$O(1)$O(1)	否
二路归并	$O(n\log_2 n)$O(nlog2​n)	$O(n\log_2 n)$O(nlog2​n)	$O(n\log_2 n)$O(nlog2​n)	$O(n)$O(n)	是
基数	$O(d(n + r))$O(d(n+r))	$O(d(n + r))$O(d(n+r))	$O(d(n + r))$O(d(n+r))	$O(r)$O(r)	是

怎么选：n 较小时用直接插入或简单选择；基本有序时用直接插入或起泡；n 较大时用快速、堆或归并，其中要求稳定的选归并，内存紧张、又怕最坏情况的选堆排序；关键字位数少而 n 很大时可用基数排序。

易错提醒

• ❌ 折半插入排序的时间复杂度是 $O(n\log_2 n)$O(nlog2​n)。✅ 它只减少了比较次数，移动次数仍是 $O(n^2)$O(n2)，总时间 $O(n^2)$O(n2)。因为找到位置后还要逐个后移元素。

• ❌ 初始序列越接近有序，快速排序越快。✅ 取第一个元素作枢轴时，有序序列正是最坏情况。因为每次划分只分出一个元素，递归深度变成 n。

• ❌ 堆排序空间复杂度是 $O(n)$O(n)。✅ 是 $O(1)$O(1)。因为堆就建在原数组里，输出的元素放在数组末尾。

• ❌ 基数排序的每一趟用什么方法分配都行。✅ 每一趟都必须是稳定的分配收集。因为高位相同时，要靠前几趟排好的低位次序。

• ❌ 外部排序增大归并路数 k，内部比较次数一定成倍增加。✅ 用败者树后每次选最小只要 $\lceil \log_2 k \rceil$⌈log2​k⌉ 次比较。因为败者树像锦标赛，只沿一条路径重赛。

例题精讲

例题 1（快速排序）

对序列 46、79、56、38、40、84、21、65 用上面的划分函数（第一个元素作枢轴）做一趟划分，写出结果。

答题要点示范：枢轴 46。high 从右往左找到 21，放到 0 号；low 从左往右找到 79，放到 21 原来的 6 号；high 继续找到 40，放到 1 号；low 找到 56，放到 4 号；high 找到 38，放到 2 号；low 右移与 high 相遇于 3 号，放入枢轴。结果为 21、40、38、46、56、84、79、65，46 已在最终位置。

例题 2（外部排序）

有 40 个初始归并段，做 5 路归并。要几趟？用败者树时每选出一个记录要比较几次？另外，若有 8 个长度不等的初始归并段做 3 路归并，构造最优归并树要补几个虚段？

答题要点示范：趟数 $\lceil \log_5 40 \rceil = 3$⌈log5​40⌉=3（$5^2 = 25 \lt 40 \le 125$52=25<40≤125）；败者树每次比较 $\lceil \log_2 5 \rceil = 3$⌈log2​5⌉=3 次；$(8 - 1) \bmod (3 - 1) = 1$(8−1)mod(3−1)=1，要补 $2 - 1 = 1$2−1=1 个虚段。

例题 3（选方法）

某系统要对约 100 万条记录按金额排序，金额相同的记录必须保持原来的先后次序，内存足够。应该选哪种排序？

答题要点示范：n 很大，排除 $O(n^2)$O(n2) 的方法；要求稳定，排除快速排序和堆排序；内存足够，$O(n)$O(n) 的辅助空间不成问题。选二路归并排序，时间 $O(n\log_2 n)$O(nlog2​n) 且稳定。

本节小结

• 插入类：直接插入最好 $O(n)$O(n)；折半插入只省比较；希尔不稳定。
• 交换类：起泡最好 $O(n)$O(n)；快速排序平均 $O(n\log_2 n)$O(nlog2​n)、有序时最坏，一趟划分后枢轴到最终位置。
• 选择类：简单选择比较次数固定；堆排序 $O(n\log_2 n)$O(nlog2​n)、$O(1)$O(1) 空间，二者都不稳定。
• 归并排序 $O(n\log_2 n)$O(nlog2​n)、$O(n)$O(n) 空间、稳定；基数排序 $O(d(n + r))$O(d(n+r))、每趟要稳定。
• 外部排序：趟数 $\lceil \log_k r \rceil$⌈logk​r⌉；败者树减比较，置换-选择减段数，最优归并树减读写，补虚段看 $(r - 1) \bmod (k - 1)$(r−1)mod(k−1)。