分治的另一种玩法：不先拆后合，而是先想办法"站好队"，站好队之后两边根本不用合并。
分治（Divide and Conquer）由三个步骤组成：
分治的威力在于：把一个 O(n²) 的问题，通过"拆成两半、各自解决"变成 O(n log n)——每次对半拆，只需要 log₂n 层，每层的总工作量是 O(n)，整体就是 O(n log n)。同样是排序问题，"分""治""合"这三步可以有不同的分工方式：上一节（9.2）的归并排序，"分"的时候什么都不做（只是简单地对半切），真正的工作量都在"合"这一步；本节要讲的快速排序正好相反——"分"这一步就已经把活干完了，"合"这一步反而几乎不需要做任何事。
快速排序的"分"是这样做的：从数组里选一个数当作基准值（pivot），然后把整个数组"重新排队"——比 pivot 小的都站到左边，比 pivot 大的都站到右边。这个"重新排队"的操作叫 partition（划分）。
partition 做完之后，会发现一件很方便的事：左边一整块都比右边一整块小，所以只需要分别对左边和右边递归排序，两边各自排好之后，根本不需要再做任何"合并"的动作——数组本来就已经是"左边一块、右边一块"排好的样子了，"合"这一步几乎是免费的。这正好和归并排序"分的时候什么都不做，合的时候要认真做"反过来。
用数组 [5, 2, 8, 1, 9, 3]、选 5 作为 pivot，看一次 partition 具体做了什么：
5（粉色）左边全是比它小的数，右边全是比它大的数——但注意：这一次 partition 不保证 pivot 本身已经站到了排序完成后的最终位置（下一节代码里会具体解释为什么）。接下来只需要对左右两段分别递归调用同样的 partition，不需要额外的合并步骤。
| 1 | void QuickSort(int a[], int l, int r) |
| 2 | { |
| 3 | if (l >= r) return; // 递归终止：区间只剩 0 或 1 个元素 |
| 4 | |
| 5 | int pivot = a[(l + r) / 2]; // 取区间中间的元素作基准值 |
| 6 | int i = l - 1, j = r + 1; |
| 7 | while (i < j) |
| 8 | { |
| 9 | do { i++; } while (a[i] < pivot); // i 从左往右，找第一个 ≥ pivot 的位置 |
| 10 | do { j--; } while (a[j] > pivot); // j 从右往左，找第一个 ≤ pivot 的位置 |
| 11 | if (i < j) { swap(a[i], a[j]); } // 两个位置都找到了，交换，让左边变小、右边变大 |
| 12 | } |
| 13 | |
| 14 | QuickSort(a, l, j); // 递归排左边这一段 |
| 15 | QuickSort(a, j + 1, r); // 递归排右边这一段 |
| 16 | } |
| 17 | |
| 18 | // 调用方式：QuickSort(a, 0, n - 1); |
do...while 而不是普通 while？因为需要 i、j 在比较之前先移动一步——如果 a[i] 恰好等于 pivot，用 do...while 能保证 i 至少往前挪一位，避免两个指针停在原地不动、死循环卡住。QuickSort(l, j) 和 QuickSort(j+1, r)，而不是按 pivot 的下标切？这种写法（叫 Hoare 划分）的 partition 结束后，只保证下标 j 左边都 ≤ pivot、右边都 ≥ pivot，但 pivot 本身具体停在哪个下标是不确定的——所以正确的切分点是 j，而不是 pivot 最初所在的下标。这是本节最容易写错的地方，下一节陷阱里会再具体展开。| 情况 | 时间复杂度 | 什么时候发生 |
|---|---|---|
| 最好 / 平均 | O(n log n) | 每次 partition 都能把数组大致分成两半 |
| 最坏 | O(n²) | 每次 partition 都极不均衡（比如一边只有 1 个元素） |
log n 层的递归深度变成了 n 层。上面代码选择区间中间的元素作为 pivot（而不是固定选第一个或最后一个），已经能避开"数组本身就有序"这种最常见的构造方式导致的最坏情况，但仍然可能被专门构造的数据卡住——更稳妥的做法是随机选择 pivot，或者"三数取中"（取首、中、尾三个数的中位数），这里先了解思路即可。j 为界，左边都小、右边都大"，pivot 本身的下标可能已经变了。递归时必须按 j 切分，如果习惯性地写成按 pivot 原来的下标切分，会漏掉或重复处理某些元素。l == r 而不是 l >= r：如果某次递归传入的区间是空的（l > r），用 l == r 判断会漏掉这种情况，导致继续访问不属于当前区间的元素，甚至无限递归。sort（背后通常已经做了这类优化）。sort。