快速排序
复习
- 分治：分、治、合
- 归并排序：分治排序，但需要额外空间
- 数组：可以就地交换元素
TL;DR
- 快速排序选一个基准，把数组划分成“小的”和“大的”两部分
- 递归处理这两部分，无需额外空间
- 平均
O(n log n)，常数小，实际很快 - 最坏可能退化成
O(n²)，取决于基准怎么选
正文
归并排序虽然稳定，但要多花一份空间。有没有又快又省地方的排序？有的——快速排序（quicksort）。它在实践中通常是最快的通用排序之一。
选个基准，两边分家
快排的核心动作叫划分（partition）：
- 从数组里挑一个元素当基准（pivot）
- 把数组重新排列：比基准小的放左边，比基准大的放右边
- 此时基准已经落在它最终该在的位置上
- 对左右两部分递归地重复这个过程
和归并排序“先分后合”不同，快排是“先整理、再分头处理”，而且整理完不需要再合并——因为划分本身就让元素各就各位了。
而且，划分可以就地完成，不需要额外的数组，比归并排序省空间。
平均很快
如果每次划分都大致对半，那递归深度约 log n 层，每层整体扫描一遍是 O(n)，总共 O(n log n)。
它的常数比归并排序小，实际运行往往更快，所以被广泛使用。
最坏的隐患
但快排有个软肋：如果基准选得不好，划分会极不均匀。
比如数组本来已经有序，而每次都选第一个元素当基准，那么每次划分都会把“其余全部”甩到一边，递归退化成一条链，深度变成 O(n)，总代价恶化到 O(n²)。这又是我们熟悉的“退化”。
缓解的办法是让基准选得随机一些，比如随机选，或三数取中（取头、中、尾的中位数）。这样就更不容易踩中最坏情况。
另外，快排是不稳定的——划分时的交换会打乱相等元素的相对顺序。所以，追求稳定就用归并，追求省空间和平均速度就用快排。取舍，永远在。
思考题 1
快速排序的“划分”在做一件什么事？
思考题 2
快速排序在什么情况下会退化成
O(n²)？怎样缓解？
小结
知识点
- 快排选基准、划分数组、递归处理两侧
- 划分可就地完成，不需额外空间
- 平均
O(n log n)，常数小、实际很快 - 基准选择不当会退化到
O(n²)，可用随机或三数取中缓解
参考资料
- Wikipedia(zh)：快速排序：基于划分的排序算法
- Wikipedia(zh)：分治法：快排的理论基础
思考题答案（仅供参考）
思考题 1
划分是围绕一个基准元素，把数组重排为“比基准小的在左、比基准大的在右”，从而使基准落到它最终应有的位置。之后再对左右两部分递归排序。
思考题 2
当基准选择使得划分极不均匀时（例如数组已有序又总选端点为基准），递归深度退化为 O(n)，总代价变成 O(n²)。缓解办法是随机选择基准或采用三数取中等策略，让划分尽量均衡。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪