比较排序

比较模型把键视为只能相互比较的对象，算法无法从某个键长得像“17”就直接知道它应该去第几个桶。它必须靠比较答案逐步排除不可能的次序。这种限制使同一个下界能覆盖许多实现，而不依赖某段排序代码。

成本单位也必须明确：一次比较可能被当成一步，但若真实键是很长的字符串，比较本身就可能读取许多字符。比较次数、元素搬移次数和总运行时间可以不同；比较最优不自动意味着缓存或辅助空间也最优。

三个互异元素有 $3!=6$ 种相对次序，深度为 $2$ 的二叉树最多有 $4$ 片叶。因此任何正确算法总有输入至少需要三次比较。归并排序理路归并排序Merge sort递归排序两半并线性合并的稳定比较排序算法。与堆排序具有 $O(n\log n)$ 最坏比较数，达到一般比较排序下界理路比较排序下界Comparison sorting lower bound任何最坏情形比较排序都需 Ω(n log n) 次比较。的渐近量级。

快速排序理路快速排序Quicksort围绕枢轴分区后递归排序子数组的比较排序算法。也是比较排序。互异键的随机枢轴版本通常给期望 $\mathrm{\Theta }(n\log n)$，某次运行却可花费二次时间；处理重复键的分区规则又会改变重复输入上的表现。模型成员身份不意味着所有成员具有相同的复杂度保证。

输入记录 $[2_a,1,2_b]$ 可以排成 $[1,2_a,2_b]$ 或 $[1,2_b,2_a]$，两者都满足普通排序规格。若要求稳定，才必须保留 $a$ 在 $b$ 前的原次序。删除其中一个 $2$ 则永远不合法：同一键并不意味着同一条记录。

计数排序用键值定位桶，基数排序读取数位，它们超出了比较接口。对输入已排序、只含少量不同键等受限类别，算法可能少做比较；这不推翻覆盖一般互异输入的最坏下界。

比较排序的下界来自完整次序的输出要求。选择算法理路选择算法Selection algorithm在未排序序列中求第 k 小元素而无需完全排序的算法族。只找第 $k$ 小项，不必区分所有排列，因而可以在线性次比较内完成；不能把完整排序的下界套给每一种顺序统计任务。

整数排序理路超越比较下界的整数排序integer sorting · non-comparison integer sorting通过有限整数宇宙、按位操作和分桶，说明排序复杂度可突破比较模型的 n log n 下界。利用有限键域、位提取或字级运算，改变的是获取键信息的方式。若底层只允许比较，即使键恰好都是整数，比较下界仍然成立。

同一比较算法还可放进不同机器模型。外存排序理路外存排序External-memory sorting在 I/O 模型中以块传输而非 CPU 比较次数衡量海量排序。计量块传输，并行算法模型理路并行算法模型parallel algorithm model · parallel computation model用总工作、关键路径、处理器数和通信成本共同描述并行算法，而不只报告理想加速比。区分总工作与关键路径；两者都需重新分析数据如何移动或操作如何并发。稳定性、原地性和比较次数也各由不同的算法机制保证。