入门：分治、分区与为什么是 O(n log n)
基于通用算法概念 · 核于 2026-07
速查
- 核心思想：快排 = 分治。三步——①选 pivot（基准）；②分区 partition（比 pivot 小的扔左、大的扔右，pivot 落到最终位置）；③对左右子区间递归。
- 一句话：选一个 pivot，把小元素挪到它左边、大元素挪到右边，再递归排两边。 这是快排的全部。
- 复杂度：平均 O(n log n)、最坏 O(n²)、空间 O(log n)（递归栈）；原地、不稳定。
- 为什么平均 O(n log n)：只要 pivot 大致把数组分成比例固定（如 9:1 也行），递归深度 O(log n)，每层分区总工作量 O(n)，相乘 O(n log n)。
- 最坏 O(n²) 的成因：pivot 选极差（输入有序还总取首元素）→ 每次分出 0 和 n-1 两段 → 退化成冒泡，递归 n 层。
- 规避最坏：随机化 pivot（期望 O(n log n)）、三数取中（首/中/末的中位数）、Introsort（递归过深切换堆排兜底）。
- 为何实际最快：①常数小（内层循环极简，只有比较和交换，没有额外内存分配）；②原地（无归并的 O(n) 辅助数组）；③缓存友好（顺序扫描连续内存，分支预测友好，比堆排的跨层跳跃快得多）。
- 稳定性：快排不稳定——分区交换会打乱相等元素的相对顺序，需要稳定排序用归并/Timsort。
- 空间：递归栈平均 O(log n)、最坏 O(n)（退化），尾递归优化后保证 O(log n)。
- 进阶顺序：分区策略 → 工程实践 → 参考。
一、快排核心思想：选 pivot、分区、递归
快排的本质是分治法（Divide and Conquer）——把「排好整个数组」分解成「排好两段子数组」，子数组排好了整体自然有序。三步走：
- 选基准（choose pivot）：从数组里挑一个元素当 pivot。最朴素是取首/末元素，工程上用随机或三数取中。
- 分区（partition）：重排数组，使
[lo, p-1]全 ≤ pivot、a[p] = pivot、[p+1, hi]全 ≥ pivot。这一步之后，pivot 已经在它的最终位置上了，后续不再动。 - 递归（recursion）：对左右两段
[lo, p-1]和[p+1, hi]分别再做「选 pivot + 分区」，直到子段长度 ≤ 1（天然有序，递归出口）。
quickSort(a, lo, hi):
if lo >= hi: return // 子段长度 ≤ 1，递归出口
p = partition(a, lo, hi) // 分区，返回 pivot 最终下标
quickSort(a, lo, p - 1) // 排左段
quickSort(a, p + 1, hi) // 排右段为什么对：每轮 partition 后 pivot 落到最终位置，问题被切成两个严格更小的子问题（长度之和 = n-1），递归必然收敛；当所有子段长度 ≤ 1 时整个数组有序。
二、分区：快排的灵魂
分区是快排唯一有「技术含量」的步骤——其余都是机械的递归。分区的目标是：选 pivot → 把小于它的挪到左、大于它的挪到右 → 返回 pivot 的最终位置。主流三种实现（详见 分区策略）：
- Lomuto 分区：单指针
i从左扫，遇到小于 pivot 的就与a[++i]交换，最后把 pivot 换到i+1。简单易写（教科书首选），但交换次数多、pivot 偏向一端、对重复元素表现差。 - Hoare 分区：双指针从两端相向，左找大、右找小，找到就交换，相遇即分区点。交换少、更接近对称，是最初版快排用的分区，工程更快。
- 三路分区（荷兰国旗）：把数组分成
<pivot、=pivot、>pivot三段，中间段直接跳过。专治大量重复元素（把原本会退化成 O(n²) 的全相等输入稳定在 O(n)）。
三、为什么平均 O(n log n)
直觉：只要 pivot 把数组分成两个非空段（哪怕 9:1 这种很不均匀的比例），递归深度都是 O(log n)；每层递归所有分区工作量加起来是 O(n)（每个元素每层被分区碰一次），所以总工作量 = 层数 × 每层工作量 = O(log n) × O(n) = O(n log n)。
更严格地，随机化快排（pivot 随机取）的期望比较次数是 2n ln n ≈ 1.39 n log₂ n，仅比信息论下界 n log₂ n 多 39%——这就是「平均 O(n log n)」的精确含义。注意：即便每次分区都是 9:1 这种极度不均，递归深度仍是 O(log n)（因为每次至少消去 1/10），仍是 O(n log n)。只有当分区极端不均到每次只消去 1 个元素（0 : n-1）时才退化。
四、最坏 O(n²) 的退化成因
当 pivot 总被选成当前段的极值（最大或最小），分区结果就是 0 : n-1——pivot 单独成段，另一段长度只减 1。递归深度变成 n 层，每层工作量 n, n-1, n-2, ..., 1，求和 O(n²)。典型触发场景：
- 输入已有序（升序或降序）+ pivot 取首/末元素：这是最经典的退化场景，新手实现几乎必中。
- 输入几乎有序（少量随机扰动）：仍然高概率退化。
- 大量重复元素 + 二路分区：每次 pivot 等于重复值时，分区失衡（重复值都堆到一边），退化。
这正是快排必须做随机化或三数取中的原因——把「敌人构造的最坏输入」的概率打散到期望意义下不可能。
五、为什么快排实际最快
理论上归并、堆排、快排都是 O(n log n)，但实测快排通常快 1.5~2 倍，原因有三：
- 常数因子小：快排内层循环只有「比较 + 交换」两条核心语句，不分配内存、不调用复杂函数；归并每次 merge 要拷贝到辅助数组，堆排每次下沉要做大量父子比较。大 O 相同，但常数差很多。
- 原地，缓存友好：分区是顺序扫描连续内存段，整块载入 CPU 缓存行（64 字节），分支预测器对「左找大右找小」的模式预测准确率高；堆排的父子跳跃（下标
2i+1、2i+2）破坏局部性，缓存 miss 频繁，这是堆排实际比快排慢的主因。 - 实际输入友好：真实数据多有局部有序性，三数取中后分区接近完美 5:5，递归深度接近理想 log₂n。
一句话：大 O 只描述渐近，决定实际快慢的是常数、内存访问模式、分支预测——快排在三方面都占优。
下一步
理解了快排的骨架（选 pivot + 分区 + 递归）后，下一步深入分区算法的细节——Lomuto vs Hoare vs 三路，以及如何靠随机化/三数取中规避最坏 O(n²)，见分区策略。