快速排序

归并排序先解决两半，再把结果合起来；快速排序先确定不同键区间之间的次序，再解决各区间内部。分区后，左段任何键都小于中间段，右段任何键都更大，因此递归结果可以直接相接，无须再作一次归并。

随机枢轴不保证每次均分，而是防止固定输入持续强迫同一极端划分。三路分区还有另一个作用：把相等键一次排除。重复值越多，可能需要的比较越少，所以不能把互异键的紧确期望界直接写成每一种输入的紧确界。

分区不变式与一条轨迹 ​

每轮开始时的循环不变式理路循环不变式Loop invariant在循环初始化后成立，并在每次循环迭代后继续成立的断言。是：$[l,lt)$ 小于 $v$，$[lt,i)$ 等于 $v$，$[i,gt)$ 尚未分类，$[gt,r)$ 大于 $v$；区间外不变，区间内的元素重数也不变。三个分支分别把一个未分类元素送入正确区域，且每轮都让 $gt-i$ 减少一，所以分区终止。

例如 $[4,1,3,2]$、$v=3$，从 $(lt,i,gt)=(0,0,4)$ 开始：

• 交换首项与末项，得到 $[2,1,3,4]$，状态 $(0,0,3)$
• $2<3$，处理后状态为 $(1,1,3)$
• $1<3$，处理后状态为 $(2,2,3)$
• $3=3$，处理后状态为 $(2,3,3)$，分区结束

下一步只排序 $[2,1]$ 和单项 $[4]$。第一步不能同时增加 $i$，因为从右端换来的 $2$ 尚未分类；如果跳过它，不变式便失效。

重复键改变哪一条结论 ​

全相等的长度 $n$ 数组在本版本中只经过 $n$ 次分类，两个递归段都为空，时间为 $\mathrm{\Theta }(n)$。若改用把所有相等键放在同一侧的 Lomuto 二路分区，每次只排除一个枢轴，即使枢轴随机，仍得到 $T(n)=T(n-1)+\mathrm{\Theta }(n)$。随机化不能修复错误套用的重复键分析。

互异键时，中间段只有一项，递推为 $T(n)=T(k)+T(n-k-1)+\mathrm{\Theta }(n)$。连续选到最小值或最大值就会平方退化。Hoare 分区返回的是分界位置，Lomuto 常返回枢轴的最终位置，本页返回一整段相等区间；三者的递归边界不能互换。

时间与辅助空间分开计算 ​

直接递归两侧时，递归栈最坏可达 $\mathrm{\Theta }(n)$；均匀随机枢轴下期望深度为 $O(\log (n+1))$。若只递归较小一侧、用循环继续处理较大一侧，每次真正新增栈帧的规模至少减半，便得到最坏 $O(\log (n+1))$ 栈空间，即使时间仍可能是二次。原地分区只表示分区本身用常数额外位置，并不抹去调用栈。

常见交换式实现不稳定。对小段切换插入排序、用三数取中选择枢轴，可能改善常数，却不能单独保证最坏 $O(n\log n)$。Introsort 在递归过深时改用堆排序等确定性后备算法，才补上最坏时间保证；快速选择则复用分区，但只继续进入包含目标秩的一侧。

若键是一字整数，整数排序理路超越比较下界的整数排序integer sorting · non-comparison integer sorting通过有限整数宇宙、按位操作和分桶，说明排序复杂度可突破比较模型的 n log n 下界。可以利用数位和字操作，已经改变了本页的比较接口。数据主要驻留外存时，外存排序理路外存排序External-memory sorting在 I/O 模型中以块传输而非 CPU 比较次数衡量海量排序。还要分析块传输；数组内的原地分区不会自动带来最优 I/O 界。