排序算法

把一列数字从小到大排好，看起来是个简单到无聊的问题。但排序是计算机科学里被研究最深、影响最广的问题之一。操作系统调度任务、数据库查找记录、搜索引擎返回结果、基因组学处理 DNA 序列——背后几乎都有排序在工作。高德纳（Donald Knuth）在《计算机程序设计艺术》第三卷整本书讲排序与搜索，不是偶然。

破除误解：没有"最好的"排序算法#

教科书常给学生一种印象：快速排序最快，学会它就够了。这是误导。没有一个排序算法在所有场景都最优。选择排序算法，需要考虑： - 数据规模（几个？几百万？） - 数据初始状态（随机？几乎有序？有很多重复？） - 内存限制（能否把数据全放进内存？） - 稳定性要求（相等的元素排序后相对顺序需要保持吗？） - 硬件特性（对缓存的友好程度）

真实系统往往使用混合策略：Python 的 Timsort（2002）、Java 的 Dual-Pivot Quicksort、C++ std::sort 都是针对实际数据分布特性精心设计的混合算法。

复杂度下界：比较排序的理论极限#

在讨论各种算法之前，有一个根本性的问题：排序能多快？ 对于只能做元素比较操作（$a < b$？）的算法，存在一个信息论下界。

对 $n$ 个不同元素排序，所有可能的排列有 $n!$ 种。每次比较把可能性减少至多一半。因此，最少需要 $\lceil \log_2(n!) \rceil$ 次比较。由 Stirling 近似：

$$\log_2(n!) \approx n \log_2 n - n \log_2 e \approx n \log_2 n$$

结论：任何基于比较的排序算法，最坏情况下必须做 $\Omega(n \log n)$ 次比较。这是不可突破的理论下界——不是技术限制，是数学事实。归并排序和堆排序达到了这个下界，是渐近最优的比较排序。

这里有个极常见的误读要先挡住：下界说的是最坏情况，不是每个输入。$n = 8$ 时 $\lceil \log_2 8! \rceil = \lceil \log_2 40320 \rceil = 16$，它保证的是"对任何比较排序算法，存在至少一个输入让它至少比 16 次"，不是"每个输入都要比 16 次以上"。40320 种排列里当然有幸运的，下一节的手算走查里快排就只花了 13 次。

主要排序算法#

冒泡排序（Bubble Sort）#

反复遍历数组，比较相邻元素并交换，把大元素"冒泡"到末尾：

for i in range(n):
    for j in range(n - i - 1):
        if arr[j] > arr[j + 1]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]
```

• 时间：$O(n^2)$ 平均和最坏
• 空间：$O(1)$（原地）
• 稳定：是
• 实际价值：几乎为零——主要作为教学例子。数据量稍大就远慢于其他算法。

归并排序（Merge Sort）#

分治策略：递归地把数组对半分，排好两半，再合并：

[8, 3, 5, 1, 9, 2]
  /              \
[8, 3, 5]     [1, 9, 2]
 /    \          /    \
[8,3] [5]     [1,9]  [2]
 / \            / \
[8] [3]       [1] [9]
合并→[3,8]  [5] → [3,5,8]   合并→[1,9] [2] → [1,2,9]
        \                   /
         → [1, 2, 3, 5, 8, 9]
```

合并操作：两个有序数组合并，只需线性扫描，$O(n)$。

• 时间：$\Theta(n \log n)$（最好、平均、最坏完全相同）
• 空间：$O(n)$（需要辅助数组）
• 稳定：是

归并排序的优点是可预测的性能——不像快速排序有退化风险，归并排序无论输入如何始终是 $O(n \log n)$。外排序（数据大于内存时在磁盘上排序）几乎都用归并排序的变种。

快速排序（Quicksort）#

选一个基准（Pivot），把数组分为小于基准和大于基准两部分，递归排序：

def quicksort(arr, lo, hi):
    if lo < hi:
        p = partition(arr, lo, hi)  # 选基准，重排数组
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)
```

• 时间：$O(n \log n)$ 平均，$O(n^2)$ 最坏（基准选得极差时，如每次选到最小/最大元素）
• 空间：$O(\log n)$ 平均（递归栈）
• 稳定：通常不是

快速排序的实际速度通常优于归并排序——常数因子更小，缓存友好性更好。$O(n^2)$ 的最坏情况通过随机选择基准（Randomized Quicksort）可以有效规避，期望时间仍是 $O(n \log n)$，最坏概率极低。

堆排序（Heap Sort）#

利用最大堆数据结构：先把数组建成堆（$O(n)$），然后反复取出堆顶最大值放到末尾，缩小堆（每次 $O(\log n)$）：

• 时间：$O(n \log n)$ 保证（无退化）
• 空间：$O(1)$（原地，这是它相对归并排序的优势）
• 稳定：不是

堆排序在理论上很优雅（最坏情况 $O(n \log n)$ + 原地），但实际比快速排序慢，因为访问模式对 CPU 缓存不友好。

手算走查：同一个数组，快排与归并各走一遍#

复杂度记号会抹掉最有意思的部分。下面把同一个 8 元素数组 8 3 5 1 9 2 7 4 交给两个算法，把每一步都写出来——拿笔就能复算。

快速排序（Lomuto 分区，pivot 固定取子数组最后一个元素）

分区的规则只有一条：从左到右扫，遇到 $\le$ pivot 的元素就把它换到"小于区"的末尾；扫完把 pivot 换到小于区之后。

四轮之后数组是 1 2 3 4 5 7 8 9，共 13 次比较，最大递归深度 3（正好是 $\log_2 8$）。这个输入对快排很友好：第一轮的 pivot 4 把 8 个元素切成 3 和 4，几乎对半。

归并排序（自底向上看每一层）

最后一次归并值得逐步看：比 1 与 2 取 1，比 3 与 2 取 2，比 3 与 4 取 3，比 5 与 4 取 4，比 5 与 7 取 5，比 8 与 7 取 7，比 8 与 9 取 8，此时左半用尽，9 直接抄过去。7 次比较，一次都没浪费。

归并共 $4 + 6 + 7 = 17$ 次比较。这张表最该注意的是 17 这个数：$n = 8$ 时归并排序的最坏比较次数正是 $n\lceil \log_2 n\rceil - 2^{\lceil \log_2 n\rceil} + 1 = 24 - 8 + 1 = 17$（Knuth 第三卷给出的公式）。也就是说，这个输入恰好让每一层的每次归并都被迫比到最后一个元素——归并排序在这里跑的是自己的最坏情况，而快排跑的是自己的好情况。

于是有了一组具体的数字对照：快排 13 次，归并 17 次，理论最坏下界 16 次。快排低于 16 不违反下界（下界管的是最坏输入），归并等于自己的最坏值也不奇怪（它的最好与最坏本来只差常数）。渐进复杂度相同的两个算法，在单个输入上的差距可以是这样来的。

失败现场：一个已经排好序的数组#

上面的快排看着很好，但它有一个致命的默认设置：pivot 固定取最后一个元素。把输入换成 1 2 3 4 5 6 7 8（已经有序），同一套代码的行为完全变了。

每轮 pivot 都是当前最大值，右半永远为空，递归退化成一条长链：比较次数 $7+6+5+\cdots+1 = 28 = \frac{n(n-1)}{2}$，递归深度 $n-1 = 7$。

把 $n$ 放大到一百万，后果不再是"慢一点"：

比较次数差约 1.8 万倍，但真正先杀死程序的是右边那一列的第二行：一百万层递归会在做完比较之前就把调用栈撑爆。已排序输入是快排最常见的现实输入之一——数据库里刚 ORDER BY 过的中间结果、日志里按时间递增的记录、被上一个环节排好又排一次的数组，全都是这个形状。

常见的三种缓解手段各有各的边界：

• 三数取中（median-of-three）：取首、中、尾三者的中位数作 pivot。对已排序输入立刻见效（中位数就是真中位数，完美对半），但 Bentley 与 McIlroy 1993 年那份经典实现仍可被专门构造的输入击穿。Java 7 起的双轴快排（Yaroslavskiy 提出）走得更远一步：从五个采样元素里取两个三分位点作双 pivot。Wild 与 Nebel 在 ESA 2012 上给出了它的精确平均分析——$1.9n\ln n - 2.46n + O(\ln n)$ 次比较，比经典单轴快排的 $2n\ln n$ 略少；有意思的是，这个改进曾被此前的理论研究判断为"不值得做"，Oracle 是靠实测数据推翻了理论上的悲观预期。
• 随机化 pivot：把"坏输入"变成"坏运气"，期望时间 $O(n\log n)$，退化概率极低。但它并非绝对安全——McIlroy 在 1999 年的《快速排序的杀手对手》里给出了一种在比较过程中动态构造输入的对手：它不预先准备数据，而是根据算法问出的每一次比较临时决定答案，在一组很温和的假设下能把任何快排实现（包括随机化的）逼到平方级。
• 限深切换：干脆放弃"保证 pivot 好"，改成"允许 pivot 坏，但坏到一定程度就换算法"。这就是下一节的 introsort。

introsort：真实的 `std::sort` 有三个开关#

课本上的快排和 C++ 标准库里的快排不是一个东西。libstdc++ 的 std::sort 实现的是 Musser 1997 年提出的 introsort（内省排序），代码里有三个明确的分支，对应三种算法：

// bits/stl_algo.h（简化）
enum { _S_threshold = 16 };

// std::sort 的入口把深度预算算好再进循环 _introsortloop(_first, last, std::lg(last - _first) * 2);

// 循环体 while (_last - first > int(S_threshold)) { if (_depthlimit == 0) { // ① 递归太深 → 堆排序 std::_partialsort(_first, last, _last); return; } --_depthlimit; // ② 否则继续快排分区 } // ③ 退出循环后统一做一次插入排序 ```

三个常数值得逐个看清楚：

1. 深度预算 $2\lfloor \log_2 n\rfloor$。$n = 10^6$ 时 $\lfloor\log_2 n\rfloor = 19$，预算 38 层。理想快排只需 20 层，所以 38 层意味着"允许 pivot 平均差一倍"；一旦超支，说明遇上了退化输入，直接切堆排序——它没有退化情况，$O(n\log n)$ 是保证。这一步把快排的最坏情况从 $O(n^2)$ 焊死成 $O(n\log n)$，代价只是极少数情况下慢一个常数因子。
2. 小数组阈值 16。子数组短于 16 个元素时不再递归，留着不管；等整个分区过程结束后，对整个数组做一次插入排序。因为此时数组已经"几乎有序"（每个元素离最终位置不超过 16 格），插入排序在这种输入上是线性的，而且没有函数调用和分区开销。
3. 先分区完再统一插入排序，而不是每个小块各排一次——少了大量函数调用，缓存也更连续。

Rust 走了另一条路：slice::sort_unstable 用的是 Orson Peters 的 pdqsort（pattern-defeating quicksort，击破模式的快排），它是 introsort 的扩展，除了限深切换外还专门识别"已排序""大量重复值""逆序"这些常见模式并走特殊路径，在这些输入上能做到线性时间。Rust 是第一个把 pdqsort 收进标准库的语言。

该记住的是：工业级排序不是"选一个算法"，而是一组阈值把三四个算法缝在一起。快排负责平均速度，堆排序负责最坏情况的兜底，插入排序负责小规模和"几乎有序"的收尾。这和跳表在 128 个元素以下改用紧凑数组是同一种工程判断——渐进复杂度只在规模足够大时才说得上话。

线性时间排序：突破下界#

基于比较的排序无法突破 $\Omega(n \log n)$，但如果可以利用数据的额外结构，可以做到 $O(n)$：

计数排序（Counting Sort）：适用于取值范围有限的整数（如 0-999）。统计每个值出现次数，直接计算每个值应放的位置。时间 $O(n + k)$（$k$ 为值域大小）。

基数排序（Radix Sort）：按位（从低位到高位）对整数逐轮稳定排序，每轮用计数排序。时间 $O(d \cdot (n + k))$（$d$ 为位数）。

这类算法的代价是：它们不是通用的——只适合特定类型的数据。

Timsort：工程实践的答案#

Python 的内置排序 sorted() 和 Java 的 Arrays.sort()（对象）使用 Timsort，由 Tim Peters 在 2002 年设计。

Timsort 的核心洞察：现实数据很少是完全随机的，常常包含已经有序的片段（称为 run）。Timsort 利用这些已有序的片段，用归并排序将其合并，而不是从头重排：

• 时间：$O(n)$ 最好（已经有序），$O(n \log n)$ 最坏
• 稳定：是

这是"理论最优"与"工程最优"之间差距的典型例子——真实数据有规律，聪明的算法利用这些规律。

galloping：当两段长度悬殊时#

Timsort 里最容易被略过的优化叫 galloping mode（疾驰模式）。普通归并是"左右各看一个，取小的"；但如果左段是 1 2 3 … 1000 而右段是 1001 1002，普通归并要老老实实比 1000 次才发现左段整段都该先走。

galloping 的做法是：当同一段连续赢了若干次，就改用指数搜索——在另一段里试探第 1、2、4、8、16… 个位置，定位到区间后再二分，把"该整块搬过去多少个元素"一次算出来。切换的门槛是常数 MIN_GALLOP，Tim Peters 把它定为 7：某一段连赢 7 次才进入 galloping；进入后若继续奏效就动态降低这个门槛（更倾向于 galloping），若两段都连赢不到 7 次就退回普通归并。

为什么不一直用 galloping？Peters 在 listsort.txt 里写明了原因：每次比较的固定开销是要算的，gallop_left/gallop_right 两个函数太复杂、编译器无法合理内联，随机数据上它比普通归并更慢。7 是一个赌注：赌"连赢 7 次"意味着数据真的有大块结构，值得为它多付一次复杂调用。

被形式验证抓出来的 bug#

Timsort 把待归并的 run 压在一个栈上，靠一组栈不变式（相邻 run 的长度必须满足 runLen[i] > runLen[i+1] + runLen[i+2]）保证栈不会太深，从而把栈数组的长度硬编码成一个常数——Java 实现里是 40。

2015 年，de Gouw、Rot、de Boer、Bubel 与 Hähnle 在 CAV 会议上发表《OpenJDK 的 java.utils.Collection.sort() 是坏的：好的、坏的与最坏情况》。他们本来只是想用 KeY 定理证明器给 Timsort 做一份机械化的正确性证明，结果证明失败，并且从失败处反推出了原因：mergeCollapse 只检查栈顶 3 个 run，无法在所有情况下恢复那条不变式；不变式一旦被破坏，run 的长度增长比预期慢，个数就会超过 40。

他们据此构造出了触发条件：长度为 67 108 864（即 $2^{26}$）的数组会让 runLen 数组越界，抛出 ArrayIndexOutOfBoundsException。同一份 Timsort 代码被 Java、Android 和 CPython 共用，三家都中。作者给出的修复是把检查范围从栈顶 3 个 run 扩到 4 个，并对修复后的版本给出了完整的机械化证明，报告提交进了 OpenJDK 缺陷库（JDK-8072909）。

这件事的意义不在于"有个 bug"，而在于它被找到的方式：Timsort 已经在几十亿台设备上跑了十三年，靠测试没暴露出来——因为触发它需要 $2^{26}$ 个元素和一段精心构造的 run 长度序列。形式验证能发现它，是因为验证不是"试很多输入"，而是"对所有输入证明一个性质"，而证不出来的地方恰好就是反例所在。

稳定性：为什么多列排序离不开它#

"稳定（stable）"的定义听起来无关紧要：值相等的元素，排序后相对顺序不变。它的价值要放到多列排序里才看得见。

假设要出一张成绩表，要求"先按班级升序，同班内按分数降序"。一种常见做法是排两遍：先按分数降序，再按班级升序。

右边这一列里，1 班内部是 92、85，2 班内部是 95、88——分数降序被完整保住了。这不是巧合：第二遍排序只看"班级"这个键，班级相同的元素在它眼里全都相等，而稳定性保证相等元素维持第一遍留下的顺序。

如果第二遍用了不稳定排序（比如快排），1 班内部完全可能变成 85、92。表面上"按班级排好了"，实际上第一遍的工作被悄悄抹掉，而且这种错误不会报错，只会在某些数据上出现、在另一些数据上不出现。

这解释了 Java 标准库里一个看起来矛盾的设计：Arrays.sort(int[]) 用不稳定的双轴快排，Arrays.sort(Object[]) 用稳定的 Timsort。原因是两个 int 值相等时它们在语义上就是同一个东西，谁在前谁在后不可观测，稳定性白送也没意义；而两个对象即使排序键相等，其余字段可能完全不同，顺序是可观测的。稳定性的成本必须付在有身份的数据上——Timsort 需要 $O(n)$ 辅助空间，双轴快排原地就够。

跨域连接#

• 信息论：下界是一个信息量论证：确定全部排列中的哪一个，需要多少比特，每次比较至多提供一比特。所以它约束的是最坏情况，不是每个输入——某个具体输入用更少的比较排完，并不违反下界，这是这条结论最常被误读的地方。
• 社会选择理论：排序默认存在一个全序的"更小"，且它可传递。当"更好"来自多个不可通约的准则时，两两比较可能出现循环，排序本身就没有定义——这与偏好聚合产生循环是同一个障碍。多准则场景下先要问的不是用哪个算法，而是那个序存不存在。
• Unicode 与数字书写：字符串的"小于"依赖语言与地区，同一批字符串在不同排序规则下顺序不同，组合字符还让"第几个字符"这件事变得含糊。于是排序的正确性有一半落在算法之外：比较函数错了，再优的算法也只是快速地给出错误答案。
• 概率论：随机选枢轴把"坏输入"变成"坏运气"，期望时间由调和数给出。但保护是有边界的：一个能根据算法每次比较临时决定答案的对手，仍可把随机化实现逼到平方级。随机化防的是预先构造的输入，不是自适应的对手。
• 形式化方法与验证：工业级排序把几个算法用阈值缝在一起，正确性依赖一组不变式。其中一处不变式被打破的缺陷，是在证明失败处反推出来的，而不是被测试撞见的——因为触发它需要极大规模加上精心构造的片段长度序列。验证与测试的差别就在这里。

参考文献#

• Knuth, D. The Art of Computer Programming, Vol. 3: Sorting and Searching. 2nd ed. Addison-Wesley, 1998.（归并排序最坏比较次数 $n\lceil\lg n\rceil - 2^{\lceil\lg n\rceil}+1$）
• Cormen, T. et al. Introduction to Algorithms (CLRS). 3rd ed. MIT Press, 2009. （第6-9章）
• Peters, T. Timsort. Python 源码注释，2002.（Objects/listsort.txt，含 MIN_GALLOP = 7 与 galloping 模式的取舍说明）
• Musser, D. R. "Introspective Sorting and Selection Algorithms." Software: Practice and Experience 27(8), 983–993, 1997.
• Bentley, J. L. & McIlroy, M. D. "Engineering a Sort Function." Software: Practice and Experience 23(11), 1249–1265, 1993.
• McIlroy, M. D. "A Killer Adversary for Quicksort." Software: Practice and Experience 29(4), 341–344, 1999.
• de Gouw, S., Rot, J., de Boer, F. S., Bubel, R. & Hähnle, R. "OpenJDK's java.utils.Collection.sort() Is Broken: The Good, the Bad and the Worst Case." CAV 2015, LNCS 9206, 273–289. DOI: 10.1007/978-3-319-21690-4_16
• Wild, S. & Nebel, M. E. "Average Case Analysis of Java 7's Dual Pivot Quicksort." ESA 2012, LNCS 7501, 825–836.
• libstdc++ 源码 bits/stl_algo.h（_S_threshold = 16、__introsort_loop 的 __lg(n) * 2 深度预算）。

延伸阅读#

• Sedgewick, R. & Wayne, K. Algorithms. 4th ed. Addison-Wesley, 2011.（第 2 章排序，含大量实测数据）
• Peters, T. listsort.txt — https://github.com/python/cpython/blob/main/Objects/listsort.txt （Timsort 设计笔记原文，读起来像工程日记）
• Peters, O. Pattern-defeating Quicksort — https://github.com/orlp/pdqsort （pdqsort 的设计说明与基准）