快速排序

快速排序选择枢轴并原地分区，把枢轴放到最终相对位置，使较小元素位于一侧、较大元素位于另一侧，再递归处理两边。合并阶段几乎为空，效率取决于分区是否持续均衡；随机枢轴让任意固定输入上的期望分割良好，而不是保证每次恰好对半。它通常缓存友好且常数小，但标准实现不稳定。

总选首元素处理已排序数组会不断产生 $0$ 与 $n-1$ 划分而平方退化；随机枢轴可消除输入顺序与坏划分的固定关联。大量重复键时，二路划分可能低效，三路划分把等于枢轴的元素集中处理。随机化结论是对算法随机性的期望，不等于每次运行保证 $O(n\log n)$。

对 $[4,1,3,2]$ 取枢轴 $3$，分区可得到 $[1,2]$, $3$, $[4]$，递归后有序。若已排序数组总取首元素为枢轴，子问题规模依次为 $n-1,n-2,\dots$，时间退化为 $\mathrm{\Theta }(n^2)$、递归栈也可达 $\mathrm{\Theta }(n)$。

Hoare 与 Lomuto 分区的返回语义不同，混用递归边界会死循环或漏元素。大量重复键时三路分区更稳健；“随机打乱”需使用足够均匀的随机源，不能只换一种确定输入顺序。

快速排序因原地分区、连续扫描和低常数常用于内存中的比较排序。工程实现常让很小的子数组转用插入排序，并用三数取中等办法改善普通输入上的枢轴质量；这些只调整常数和坏划分频率，不提供最坏界。随机枢轴给任意固定输入上的期望 $\mathrm{\Theta }(n\log n)$ 比较，却仍有 $\mathrm{\Theta }(n^2)$ 单次最坏；加入深度上限形成 introsort，才由确定性后备算法恢复最坏 $O(n\log n)$。同一 partition 原语也用于 quickselect，但只递归一侧。

若键是一字整数，超越比较的整数排序公理库超越比较下界的整数排序integer sorting · non-comparison integer sorting通过有限整数宇宙、按位操作和分桶，说明排序复杂度可突破比较模型的 n log n 下界。可利用数位与字操作，问题已不受快速排序的比较决策树约束。数据驻留外存时，外存排序公理库外存排序External-memory sorting在 I/O 模型中以块传输而非 CPU 比较次数衡量海量排序。以块传输为成本，快速排序的原地局部性不自动达到最优 I/O 界；应把比较数、RAM 时间、递归栈和 I/O 分别报告。