快速排序的原理是什么？为什么它平均最快、最坏又会退化？

简化版

快速排序是分治：选一个基准（pivot）,通过一次分区（partition） 把数组分成「比基准小的」和「比基准大的」两部分（基准归位到中间）,再对左右两部分递归快排。平均 O(n log n) 且常数小、原地、缓存友好,所以实际最快;但最坏 O(n²)（每次基准都选到最大/最小,分区极不平衡,如对已排序数组用固定基准）。不稳定。用随机化 / 三数取中避免最坏。

详细版

void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);   // 分区,返回基准最终位置
    quickSort(a, lo, p - 1);        // 递归排左半（都比基准小）
    quickSort(a, p + 1, hi);        // 递归排右半（都比基准大）
}
// Lomuto 分区（以最后一个元素为基准）
int partition(int[] a, int lo, int hi) {
    int pivot = a[hi], i = lo;      // i 指向「小于基准区」的下一个位置
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) { swap(a, i, j); i++; } // 比基准小的换到左边
    }
    swap(a, i, hi);                 // 基准归位到 i
    return i;
}

分区是核心:一趟扫描把小于基准的甩到左边、大于的留右边,基准落到最终位置。
递归:对基准左右两侧分别快排。基准一旦归位就永不再动。
平均每次把数组分成两半,递归 log n 层、每层 O(n) 分区 → O(n log n)。

完整版教学

一、核心思想:分区 + 分治

快速排序的灵魂是分区(partition):选一个基准值,把数组重新排列成「左边都比基准小、右边都比基准大」,此时基准就到了它最终该在的位置(左边的都比它小、右边都比它大)。然后对左右两部分递归做同样的事。和归并排序「先递归再合并」相反,快排是「先分区(在划分时就干活),再递归,无需合并」——分完区左右两半各自排好,整个数组就有序了。

二、分区怎么做(以 Lomuto 为例)

以最后一个元素为基准,用一个指针 i 维护「小于基准区」的边界:

遍历 j 从 lo 到 hi-1。
如果 a[j] < 基准,就把它交换到「小于区」末尾(swap(i, j)),i++。
遍历完,把基准(a[hi])交换到 i 位置——此时 i 左边全比基准小、右边全比它大。
返回 i(基准最终位置)。

另一种常见分区是 Hoare 分区(双指针从两端向中间夹),交换次数更少、效率更高,是很多库的选择,但边界处理更易错。Lomuto 更好理解,面试常写它。

三、为什么平均 O(n log n)

理想情况下,每次分区都把数组均分成两半。那么递归树有 log n 层,每一层所有分区加起来要扫 O(n) 个元素,总共 O(n log n)。即使分区不完全均匀(比如 1:9),只要比例固定,层数仍是 O(log n),平均仍是 O(n log n)。数学上可以证明快排的平均比较次数约 1.39·n·log₂n,常数很小。

四、为什么最坏 O(n²)（重点）

快排的最坏情况出现在每次分区都极度不平衡——基准恰好是当前区间的最大或最小值,分完一边是空、另一边是 n-1 个。这样递归深度变成 n 层,每层 O(n),总共 O(n²)。

最经典的触发场景:用「固定取第一个/最后一个元素」做基准,去排一个已经有序(或逆序)的数组。此时每次选的基准都是极值,分区完全失衡,退化成 O(n²),还可能递归过深导致栈溢出。这是快排最大的坑。

五、如何避免最坏:随机化与三数取中

既然最坏来自「基准总选到极值」,那就让基准的选择避开可预测的极值:

随机化:每次从区间里随机挑一个元素当基准(和末尾交换后再分区)。这样任何特定输入都不能稳定触发最坏,期望仍是 O(n log n)。
三数取中(median-of-three):取「首、中、尾」三个元素的中位数当基准,能避免对有序数组的退化,实践中很常用。
introsort(内省排序):快排递归太深(超过 log n 的常数倍)时,自动切换到堆排序,把最坏兜底到 O(n log n)——C++ STL 的 sort 就是它。

六、为什么快排「实际最快」

同为 O(n log n),快排在实际中通常比归并、堆排快,原因:

原地排序:只需 O(log n) 的递归栈,不像归并要 O(n) 辅助数组、频繁分配拷贝。
缓存友好:分区是顺序扫描连续内存,CPU 缓存命中率高;堆排序的跳跃式访问(父子下标 2i)缓存差。
常数小:分区的内层操作简单。

所以「渐进复杂度相同,常数和缓存决定实际速度」,快排在这两点上都赢。

七、复杂度与稳定性小结

时间:平均、最好 O(n log n);最坏 O(n²)(基准总选极值)。
空间 O(log n):递归栈(平均);最坏 O(n)。
不稳定:分区中的远距离交换会打乱相等元素的相对顺序。
优化:随机化/三数取中防退化、小子数组切插入排序、introsort 兜底。

八、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：分区结束后枢轴位于最终位置，左侧不大于它、右侧不小于它。

对应的状态推进是：选择枢轴、原地分区，再递归处理枢轴两侧；随机化降低持续劣分风险。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。平衡时 T(n)=2T(n/2)+Θ(n)=O(n log n)，单边分区时 O(n²)。

带数字走一遍：[3,2,1,5,4] 以 3 分区可得到 [2,1,3,5,4]，3 不再参与递归。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	内存数组通用排序常用，但需要随机枢轴、三路分区和小区间优化
时间复杂度	平均 O(n log n)，最坏 O(n²)
额外空间	平均栈 O(log n)，最坏 O(n)
关键边界	大量重复值宜用三路分区；递归先处理较小侧可限制栈深
替代方案	需要稳定性或最坏保证时考虑归并/堆排序

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

九、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“内存数组通用排序常用，但需要随机枢轴、三路分区和小区间优化”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写平均 O(n log n)，最坏 O(n²) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“平衡时 T(n)=2T(n/2)+Θ(n)=O(n log n)，单边分区时 O(n²)”。
误区：重复值和边界值不会改变代码。 大量重复值宜用三路分区；递归先处理较小侧可限制栈深。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“分区结束后枢轴位于最终位置，左侧不大于它、右侧不小于它”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[3,2,1,5,4] 以 3 分区可得到 [2,1,3,5,4]，3 不再参与递归”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“需要稳定性或最坏保证时考虑归并/堆排序”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

十、加强记忆

快速排序 = 分治 + 分区:选基准,一趟 partition 把数组分成「小于基准 | 基准 | 大于基准」,基准归位后递归排左右两半(无需合并)。平均 O(n log n)(每次约均分,log n 层×每层 O(n))、常数小、原地、缓存友好,所以实际最快;最坏 O(n²)(基准总选极值,如固定基准排有序数组,还可能栈溢出)、不稳定。用随机化 / 三数取中防退化,introsort 用堆排序兜底最坏。

简化版

详细版