比较排序的下限（进阶）
复习
- 计数排序与基数排序：不靠比较的排序
- 归并排序与快速排序：
O(n log n) - 大 O 记号：描述增长量级
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
TL;DR
- 只靠两两比较的排序，至少要
Ω(n log n)次比较 - 这个下界来自“决策树”的论证
- 它说明
O(n log n)已经是最优的一类 - 计数排序等更快，是因为它们不靠比较
正文
归并、快排、堆排，都能做到 O(n log n)。为什么没有更快的比较排序？这一章给出一个很漂亮的回答：因为它们不可能更快。
把所有选择画成一棵树
只靠比较的排序，本质上是在做一连串判断：“A 比 B 大吗？”每次比较只有两种结果，于是整个决策过程可以画成一棵二叉树——每个节点是一次比较，两条分支对应两种结果。
在这棵树里，从根走到某个叶子，就代表了一次完整的判断过程，而叶子对应一种最终的排列顺序。
关键来了：
- n 个元素，一共有
n!种可能的排列 - 要想区分所有情况，决策树至少要有
n!个叶子 - 一棵高度为 h 的二叉树，最多只有
2ʰ个叶子
于是有了下界
要装下 n! 个叶子，树的高度 h 必须满足 2ʰ ≥ n!，也就是 h ≥ log₂(n!)。
利用一个近似，log₂(n!) 约等于 n log n 的量级。所以：
任何只靠比较的排序，最坏情况下至少要
Ω(n log n)次比较。
这说明归并、快排、堆排已经摸到了比较排序的理论天花板——不可能有渐近更快的比较排序了。
那线性排序怎么来的
你可能会问：前面计数排序明明是线性的，不就和这个下界矛盾了吗？
不矛盾。因为下界只适用于**“只靠比较”的排序。计数排序、基数排序绕开了比较，转而利用数据的取值范围、位数**这些额外信息。它们打破了比较排序的天花板，靠的是对数据提出更多的先决条件。
这又是一次熟悉的启示：定理给出的限制，往往也指明了突破的方向——换一种前提，就能走出另一条路。
思考题 1
为什么只靠比较的排序，无法普遍快过
O(n log n)？
思考题 2
计数排序能达到线性级别，这与比较排序的下界矛盾吗？
小结
知识点
- 比较排序可建模为决策树
- n 个元素有
n!种排列，树高至少log₂(n!) - 因此比较排序下界为
Ω(n log n) - 非比较排序靠额外前提突破这一下界
参考资料
- Wikipedia(zh)：比较排序：仅依靠比较的排序算法及其下界
- Wikipedia(zh)：大O符号：描述算法复杂度的记号
思考题答案（仅供参考）
思考题 1
因为只靠比较的排序每一步只有两个结果，整个过程对应一棵二叉树。要区分 n! 种排列，树高至少要 log₂(n!)，约为 n log n 量级。因此不存在渐近更快的比较排序。
思考题 2
不矛盾。这个下界只约束“只靠比较”的排序。计数排序不进行比较，而是利用数据的取值范围直接统计位置，因此不受该下界限制。它更快，是以对数据提出额外要求为代价的。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪