为什么比较排序最快只能是 O(n log n)？一个反直觉的信息论下界

学完插入、选择、冒泡，你可能会想：是不是有某个更聪明的比较排序，能把最坏情况也压到 O(n)？答案令人意外：不可能。只要排序只靠"两两比较"，最坏情况就至少要做 Ω(n log n) 次比较。这是理论的硬边界，不是暂时没找到好算法。

证明只用一棵树。把任何比较排序的执行过程画成一棵二叉树：每个内部节点是一次"a[i] 与 a[j] 比大小"的分支，每条从根到叶子的路径对应一种输入下的执行轨迹，而每个叶子对应一种可能的排列结果。n 个不同元素共有 n! 种排列，所以决策树至少有 n! 个叶子。

一棵有 L 个叶子的二叉树，高度至少是 log₂(L)。因此从根到任一叶子的比较次数（路径长度）至少是 log₂(n!)。用Stirling 近似可得：

最坏情况下必有一条路径最长，所以任何比较排序的最坏比较次数 ≥ Ω(n log n)。归并、堆排序恰好达到这个下界，是最优的；快排平均达到、最坏没达到；而插入/选择/冒泡远低于它。

重要推论：想突破 O(n log n)，就不能只靠比较。当数据满足额外结构（如整数且范围有限），计数排序、基数排序、桶排序（今日第⑧篇与缺口 B5）可以做到线性时间——它们用的不是"比较"，而是"直接定位"。这正是算法设计的核心智慧：下界告诉你上限在哪，也告诉你该往哪个方向绕过去。

关联推荐

• 算法与问题求解入门 — 先建立"效率用大 O 度量"的直觉
• 从冒泡到快排 — 看不同排序如何逼近或远离这个下界
• P vs NP：世纪难题 — 另一类关于"难度的极限"的思考