形式陈述

比较排序只通过询问两个元素的相对次序来获得键信息，目标输出原元素的非降排列。执行可表示为决策树：内部节点是比较，叶节点对应可能排列。对 $n$ 个互异元素，任何确定性比较排序在最坏情况下至少需要

$$\lceil {\log }_2(n!)\rceil =\mathrm{\Omega }(n\log n)$$

次比较。

直觉

比较模型隐藏具体键值，只允许比较，因此算法必须从比较答案中辨认众多可能输入次序。计数信息量给出统一下界。

例子与边界

归并排序和堆排序是 $O(n\log n)$ 的比较排序；插入排序最坏为 $O(n^2)$。计数排序与基数排序利用键的额外结构，不受比较模型下界直接约束。稳定性与原地性是另外的指标。

推论与应用

比较模型用于证明排序最优性、选择算法界和比较型数据结构下界。工程实现还需考虑移动次数、缓存与分支预测。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, Chapters 6–8。
• Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998, Chapter 5。