第 8 章 · 排序

排序是数据结构课的「期中大考」:它把前七章的知识全部调动起来(递归、树、堆、复杂度),又有一条教科书不常明说的暗线,没有万能的排序,每个算法都赢在某个具体场景。本章的策略:三个 O(n²) 的「朴素三兄弟」快速过(它们不是废物,是工业算法的零件),主力放在快排、归并、堆排的三方对峙,最后用「稳定性」这个被低估的维度把选择逻辑收束成一张表。开章先立一条铁证:为什么「O(n log n)」是内排序的天花板。

8.1 为什么 n log n 是下限

基于比较的排序,每次比较只有「小于/不小于」两种结果,n 个元素有 n! 种排列,要区分它们至少需要 log₂(n!) 次比较(决策树论证),由斯特林近似 log₂(n!) ≈ n log n。所以任何比较排序都逃不出 O(n log n)。这个下限同时指出了越狱路线:不走比较(计数、基数排序按值域直接定位,见 8.5),可以做到 O(n+k)。想通这一点,整个排序版图就位:比较系内卷 log n,非比较系用「值域可枚举」这个前提换线性。

8.2 朴素三兄弟:先认识,再拆零件

冒泡(相邻逆序就交换,每轮把最大值「冒」到末尾)、选择(每轮选最小放前面)、插入(把新元素插进已排序前缀),三者都 O(n²),但个性迥异,而且插入排序有个隐藏大招:

void insertion(int *a, int n) {
    for (int i = 1; i < n; i++) {
        int k = a[i], j = i - 1;
        while (j >= 0 && a[j] > k) { a[j + 1] = a[j]; j--; }
        a[j + 1] = k;
    }
}

它的循环次数是「逆序对数」:数组基本有序时,内层几乎不跑,整体接近 O(n)。这个性质让插入排序成为所有高性能排序的小规模终点:工业级快排递归到小区间(几十个元素)就切换成插入排序,因为此时常数(递归开销、缓存)主导,插入反而快。教材把三兄弟当反面教材,工程里它们是精密仪器的零件。

8.3 快排:分治的代表作

快排三步:选轴(pivot)、划分(小的甩左边大的甩右边)、递归两侧。划分是灵魂:

int partition(int *a, int lo, int hi) {   // 挖坑法
    int p = a[lo], i = lo, j = hi;        // 以 a[lo] 为轴(演示用,实战要随机)
    while (i < j) {
        while (i < j && a[j] >= p) j--;
        a[i] = a[j];                       // 右侧捡小填左坑
        while (i < j && a[i] <= p) i++;
        a[j] = a[i];                       // 左侧捡大填右坑
    }
    a[i] = p;
    return i;                              // 轴的最终位置
}
void quicksort(int *a, int lo, int hi) {
    if (lo >= hi) return;
    int m = partition(a, lo, hi);
    quicksort(a, lo, m - 1);
    quicksort(a, m + 1, hi);
}

平均 O(n log n)、原地 O(log n) 栈空间、缓存友好(顺序扫),综合性能之王。两个必须管理的软肋:最坏 O(n²) 发生在划分极不均匀时(有序数组 + 固定取首元素为轴),解法是随机选轴或三数取中;不稳定(划分的长距离交换会跳过相等元素)。稳定被丢掉的那一刻要心里有数:排序「订单按金额」再按「时间」,不稳定排序会打乱时间序,业务上就是事故。

8.4 归并与堆排:另两条 O(n log n) 路线

归并:分到最小、两两合并,merge 时 <= 取左半(相等时先左),天然稳定;代价 O(n) 辅助数组。它的稳定性 + 顺序访问特性让它在两个场景称王:链表排序(链表不适合快排的随机划分,归并只需改指针)、外排序(磁盘上 10GB 文件排序,内存装不下,读块、排序、写块、多路归并,数据库外部排序和 MapReduce 的 shuffle 都是它)。

堆排:第 5 章的堆原样复用,建堆 O(n),反复「取顶放末尾」O(n log n),原地、不稳定。纯速度对决它输给快排(堆的访问模式上下跳跃,缓存不友好,第 12 章内存视角会算这笔账),但它的「取最值」半程独立有用:海量数据取前 K 大(维护 K 大小的最小堆,流式处理 10 亿数据只占 K 个元素的内存),这是面试出场率最高的堆题。

排序	平均	最坏	空间	稳定	一句话定位
插入	O(n²)(近有序时 O(n))	O(n²)	O(1)	稳	小规模终点
快排	O(n log n)	O(n²)	O(log n)	否	通用内排序之王
归并	O(n log n)	O(n log n)	O(n)	稳	外排序、链表
堆排	O(n log n)	O(n log n)	O(1)	否	原地 + Top-K
计数	O(n+k)	O(n+k)	O(k)	稳	小整数值域

8.5 计数排序与「越狱」

值域小的整数(比如成绩 0100、年龄 0150)可以不走比较:开一个值域数组计数,再顺序展开,O(n+k) 且稳定(稳定版要前缀和算「每个值排到哪」)。把它逐位推广就是基数排序(按个位、十位……依次稳定排序),手机号排序、后缀数组构造都靠它。看清这个分层:比较排序的 log n 下限、非比较的线性越狱、各自的前提,三条界线画清,排序章就算真正毕业。

常见错误

• 快排忘记随机化。线上服务的排序输入常是「基本有序的」(时间序列),固定轴的快排直接退化 O(n²),接口超时。一行 swap(a[lo], a[lo+rand()%(hi-lo+1)]) 的事。
• 归并的 merge 边界写错。mid = lo + (hi-lo)/2 之后右半起点是 mid+1,写成 mid 会死循环;合并结束的收尾两个 while 也常漏一个。
• 不稳定排序用在多级排序。先按 A 排再按 B 排,第二趟的稳定排序才能保留 A 的序;顺序反了或用了不稳定算法,结果随机。

练习

1. 动手:实现三路划分的快排(小于、等于、大于轴),在「大量重复元素」的数据上和普通快排对比耗时,解释为什么三路能赢(等于轴的元素不再参与递归)。
2. 手算:序列 [5,2,4,6,1,3] 分别跑插入排序和快排(取首元素为轴),列出每步的数组状态;数一数插入排序的比较次数和逆序对数,验证「逆序对数」理论。
3. 动手:生成 100 万随机整数,分别用快排、归并、堆排计时(同机同数据),给三个数字排序并解释差距来源(缓存、递归、交换)。
4. 思考:10GB 的日志文件要排序,内存只有 1GB。设计一个外排序流程(分块、内排、多路归并),估算每阶段的磁盘 IO 量,再想想为什么归并是这里唯一现实的选择。