罗罗编程学习记录
本页内容 展开查看

02.5.2.2 快排与三路划分

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序 / 02.5.2 排序算法与设计

02.5.2.2-001 快速排序的基本思想是什么?

一句话结论

分治:选 pivot 把数组划分为小于、等于、大于三部分,递归排序两侧;平均 O(n log n),原地,不稳定;核心是 partition 把基准放到最终位置。

概念解释

  • 分治划分。
  • pivot 定位。
  • 两侧递归。

原理流程

  1. 选基准。
  2. 划分区间。
  3. 递归左右。

代码 / 图示

[< pivot] [pivot] [> pivot]

常见误区

  • 误区:快排稳定;正解:跨距交换不稳定。
  • 误区:快排最坏仍 O(n log n);正解:退化 O(n²)。

追问

  • Q:pivot 最终位置? A:划分后即其排序最终下标。
  • Q:快排平均为什么快? A:常数小、缓存局部性好。

02.5.2.2-002 Lomuto 划分怎么做?

一句话结论

取末元素为 pivot;指针 i 指向小于区末尾;遍历 j,小于 pivot 则交换 i+1 与 j 并推进 i;最后交换 i+1 与 pivot;返回基准下标。

概念解释

  • 小于区边界。
  • 遍历交换。
  • 基准归位。

原理流程

  1. pivot = 末元素。
  2. j 遍历,小于则扩小于区。
  3. 基准换到分界。

代码 / 示例

int partition(int[] a, int l, int r) {
    int pivot = a[r], i = l - 1;
    for (int j = l; j < r; j++) {
        if (a[j] < pivot) { i++; swap(a, i, j); }
    }
    swap(a, i + 1, r);
    return i + 1;
}

常见误区

  • 误区:小于区指针初始错位;正解:i=l-1。
  • 误区:等于 pivot 也交换;正解:Lomuto 只划小于,等于留在右侧。

追问

  • Q:Lomuto 重复元素退化? A:等于 pivot 全在一侧,可用三路划分。
  • Q:返回下标含义? A:基准最终位置。

02.5.2.2-003 Hoare 划分怎么做?

一句话结论

双指针从两端向中间:左找大于 pivot,右找小于 pivot,交换;相遇时划分;划分点不保证是 pivot 最终位置;交换次数通常少于 Lomuto。

概念解释

  • 双指针相向。
  • 逆序对交换。
  • 相遇分界。

原理流程

  1. 选基准。
  2. 左扫过小于,右扫过大于。
  3. 交换逆序对直到相遇。

代码 / 示例

int hoare(int[] a, int l, int r) {
    int pivot = a[l + (r - l) / 2], i = l - 1, j = r + 1;
    while (true) {
        do i++; while (a[i] < pivot);
        do j--; while (a[j] > pivot);
        if (i >= j) return j;
        swap(a, i, j);
    }
}

常见误区

  • 误区:Hoare 返回基准下标;正解:返回分界,两侧递归区间按 j 划分。
  • 误区:指针越界;正解:比较条件与边界配合。

追问

  • Q:两种划分哪个快? A:Hoare 交换少,Lomuto 更直观。
  • Q:pivot 选中点? A:缓解有序退化。

02.5.2.2-004 pivot 怎么选才能避免退化?

一句话结论

固定端点在已有序/逆序数据上退化 O(n²);随机选 pivot 或三数取中(左中右中位数)降低最坏概率;随机化把最坏交给概率,期望 O(n log n)。

概念解释

  • 退化原因。
  • 随机化。
  • 三数取中。

原理流程

  1. 随机选下标交换到端点。
  2. 或取左中右中位数。
  3. 再划分。

代码 / 示例

int idx = l + new Random().nextInt(r - l + 1);
swap(a, idx, r);

常见误区

  • 误区:固定取末元素仍声称 O(n log n);正解:最坏 O(n²)。
  • 误区:随机化消除最坏;正解:期望优化,理论最坏仍存在。

追问

  • Q:三数取中怎么选? A:比较 l、mid、r 取中位数放端点。
  • Q:工程排序 pivot 策略? A:混合策略,具体实现待确认。

02.5.2.2-005 快排递归复杂度怎么推?

一句话结论

划分均衡时每层 O(n),递归深度 O(log n),总 O(n log n);最差划分极不均衡,递归深度 O(n),总 O(n²);递归栈 O(log n) 平均,最坏 O(n)。

概念解释

  • 每层线性。
  • 深度对数/线性。
  • 乘积复杂度。

原理流程

  1. 划分 O(n)。
  2. 递归树深度。
  3. 层代价求和。

代码 / 图示

均衡:n + 2·n/2 + … = O(n log n)
最差:n + (n-1) + … = O(n²)

常见误区

  • 误区:快排空间 O(1);正解:递归栈 O(log n) 平均。
  • 误区:划分代价 O(1);正解:每轮扫描区间 O(n)。

追问

  • Q:尾递归优化? A:先排短侧,控制栈深,长侧迭代。
  • Q:平均复杂度证明? A:随机 pivot 期望递归树对数高。

02.5.2.2-006 快排最坏退化怎么缓解?

一句话结论

随机/三数取中选 pivot;小区间切换插入排序;三路划分处理大量重复;递归先排短侧控制栈深;退化最坏 O(n²) 理论上仍存在,靠概率与优化缓解。

概念解释

  • pivot 优化。
  • 小规模切换。
  • 重复处理。

原理流程

  1. 随机化基准。
  2. 短区间插入。
  3. 重复元素三路。

代码 / 图示

随机 pivot + 插入阈值 + 三路划分

常见误区

  • 误区:优化后无最坏;正解:理论最坏仍 O(n²),概率极低。
  • 误区:小区间用快排递归;正解:阈值下插入更省常数。

追问

  • Q:插入阈值多少? A:常见 10 左右,具体按基准测试,待确认。
  • Q:递归栈爆掉? A:先递归短侧,长侧循环迭代。

02.5.2.2-007 三路划分解决什么问题?

一句话结论

把区间分为 < pivot、== pivot、> pivot 三段;大量重复元素时等于段不再参与递归,避免重复元素导致的退化;荷兰国旗问题即三路划分。

概念解释

  • 三段分区。
  • 等于段跳过。
  • 重复友好。

原理流程

  1. 维护 lt、gt、i 三指针。
  2. 小于换 lt 后扩,大于换 gt 后扩。
  3. 等于跳过。

代码 / 示例

void threeWay(int[] a, int l, int r) {
    int pivot = a[l];
    int lt = l, gt = r, i = l;
    while (i <= gt) {
        if (a[i] < pivot) swap(a, lt++, i++);
        else if (a[i] > pivot) swap(a, i, gt--);
        else i++;
    }
    // [l, lt-1] < pivot, [lt, gt] == pivot, [gt+1, r] > pivot
}

常见误区

  • 误区:大于交换后 i 立即推进;正解:换回的元素未比较,i 不动。
  • 误区:等于段继续递归;正解:等于段已就位,跳过。

追问

  • Q:LC 75 颜色分类? A:三路划分 0/1/2。
  • Q:三路划分稳定吗? A:仍不稳定。

02.5.2.2-008 快排为什么不稳定?

一句话结论

partition 跨距交换可能把相等元素换到另一侧,打乱原始相对次序;Lomuto/Hoare/三路都存在跨距交换;需要稳定排序时选归并。

概念解释

  • 跨距交换。
  • 等值次序。
  • 稳定性破坏。

原理流程

  1. 相等元素被不同交换移动。
  2. 相对次序可能反转。
  3. 判定不稳定。

代码 / 图示

等值元素跨距交换 → 次序改变

常见误区

  • 误区:等于 pivot 不交换就稳定;正解:两侧跨距交换仍可能打乱。
  • 误区:三路划分变稳定;正解:只是优化重复,仍不稳定。

追问

  • Q:怎么改造稳定快排? A:额外空间复制分区,代价 O(n)。
  • Q:工程排序对象为什么不用快排? A:稳定性需求,见 02.5.2.1-011。

02.5.2.2-009 快排递归空间怎么控制?

一句话结论

递归栈深度等于递归树高;均衡 O(log n),最差 O(n);实现时先递归较短一侧,长侧用循环迭代,保证栈深 O(log n);辅助数组不需要。

概念解释

  • 栈深 = 树高。
  • 短侧优先。
  • 迭代长侧。

原理流程

  1. 划分得两侧长度。
  2. 先递归短侧。
  3. 长侧改循环继续。

代码 / 图示

先排短区间,长区间循环接管

常见误区

  • 误区:两侧都递归导致深链爆栈;正解:短侧优先迭代长侧。
  • 误区:快排 O(1) 空间;正解:递归栈需标注。

追问

  • Q:最坏栈深? A:O(n),退化链。
  • Q:迭代快排? A:显式栈存区间,深度可控。

02.5.2.2-010 快速选择(LC 215 第 K 大)怎么做?

一句话结论

复用 partition:划分后看基准位置与目标 K 的关系,只递归目标所在一侧;平均 O(n),最坏 O(n²)(随机化缓解);求第 K 大转第 n-K+1 小。

概念解释

  • 只排一侧。
  • 位置比较。
  • 平均线性。

原理流程

  1. partition 得基准下标。
  2. 比较目标位置。
  3. 命中返回,否则单侧递归。

代码 / 示例

public int findKthLargest(int[] a, int k) {
    int target = a.length - k; // 第 K 大 → 第 target 小
    int l = 0, r = a.length - 1;
    while (l <= r) {
        int p = partition(a, l, r);
        if (p == target) return a[p];
        if (p < target) l = p + 1;
        else r = p - 1;
    }
    return -1;
}

常见误区

  • 误区:第 K 大直接按 K 比较;正解:转换为第 n-K+1 小。
  • 误区:两侧都递归;正解:只走目标侧。

追问

  • Q:堆做法对比? A:O(n log K),见 02.3.2.4。
  • Q:最坏 O(n²) 怎么办? A:随机 pivot 期望线性。

02.5.2.2-011 快速选择复杂度怎么推?

一句话结论

平均每次划分扫当前区间,期望区间按常数比例缩小,总 O(n) 几何级数;最坏每次偏一侧 O(n²);随机化 pivot 后期望线性;空间 O(log n) 递归或 O(1) 迭代。

概念解释

  • 单侧收缩。
  • 几何级数。
  • 期望线性。

原理流程

  1. 划分 O(m)。
  2. 期望剩余 αm。
  3. 求和 n(1+α+α²+…) = O(n)。

代码 / 图示

n + αn + α²n + … = O(n)

常见误区

  • 误区:快速选择 O(n log n);正解:平均 O(n)。
  • 误区:最坏也是线性;正解:退化 O(n²)。

追问

  • Q:为什么比全排序快? A:不排序另一侧。
  • Q:求前 K 个? A:找到第 K 后收集,或堆维护。

02.5.2.2-012 快排与归并怎么对比?

一句话结论

快排原地、常数小、平均快,但不稳定且最坏退化;归并稳定、最坏 O(n log n),但需 O(n) 额外空间;内存充足且要稳定选归并,空间敏感选快排。

概念解释

  • 空间。
  • 稳定性。
  • 最坏口径。

原理流程

  1. 对比空间与稳定。
  2. 对比最坏复杂度。
  3. 按约束选型。

代码 / 图示

快排:原地 不稳 平均快
归并:O(n) 稳 最坏稳

常见误区

  • 误区:快排比归并快所以总选快排;正解:稳定/链表场景归并更合适。
  • 误区:归并原地可做;正解:标准归并需辅助数组。

追问

  • Q:链表排序用哪个? A:归并,指针合并无需额外节点数组。
  • Q:外部排序? A:归并分治,见 02.5.2.4。

02.5.2.2-013 小区间为什么切换插入排序?

一句话结论

快排递归到小规模区间时,递归开销与常数超过插入排序;阈值以下改插入,减少递归调用与划分常数;不改变渐近复杂度,优化实际运行。

概念解释

  • 小规模常数。
  • 递归开销。
  • 混合优化。

原理流程

  1. 区间长度低于阈值。
  2. 改插入排序。
  3. 不再递归划分。

代码 / 示例

if (r - l < 10) { insertionSort(a, l, r); return; }

常见误区

  • 误区:阈值改变渐近复杂度;正解:只优化常数。
  • 误区:阈值越大越好;正解:过大退化为插入 O(n²)。

追问

  • Q:阈值取值? A:经验值,基准测试确定,待确认。
  • Q:TimSort 类似思路? A:插入 + 归并混合。

02.5.2.2-014 荷兰国旗问题(LC 75)怎么做?

一句话结论

三色(0/1/2)用三路划分一次扫描排好:lt 边界 0,gt 边界 2,i 扫描中间 1;O(n) 时间 O(1) 空间;是三路划分的直接应用。

概念解释

  • 三色分区。
  • 单趟扫描。
  • 边界指针。

原理流程

  1. lt=0, gt=n-1, i=0。
  2. 0 换 lt,2 换 gt,1 跳过。
  3. i 越过 gt 结束。

代码 / 示例

public void sortColors(int[] a) {
    int lt = 0, gt = a.length - 1, i = 0;
    while (i <= gt) {
        if (a[i] == 0) swap(a, lt++, i++);
        else if (a[i] == 2) swap(a, i, gt--);
        else i++;
    }
}

常见误区

  • 误区:2 交换后 i 推进;正解:换回的是未检查值,i 不动。
  • 误区:计数排序两遍;正解:三路一趟即可。

追问

  • Q:计数排序版本? A:统计 0/1/2 次数回填。
  • Q:颜色多于三色? A:推广三路分区需扩展指针。

02.5.2.2-015 快排有哪些边界用例?

一句话结论

空数组、单元素、已有序、逆序、全相等、两元素、大量重复、极值;检查 pivot 退化、三路等于段与递归终止。

概念解释

  • 空与最短。
  • 退化序列。
  • 重复极值。

原理流程

  1. 空/单点返回。
  2. 有序测退化。
  3. 重复测三路。

代码 / 图示

[] / [1] / 升序 / 逆序 / 全相等

常见误区

  • 误区:全相等用普通两路划分退化;正解:三路跳过等于段。
  • 误区:递归终止 l<r 写错;正解:l>=r 返回。

追问

  • Q:两元素划分? A:一次 partition 就位。
  • Q:极值比较溢出? A:避免减法比较。

02.5.2.2-016 快排常见错误有哪些?

一句话结论

pivot 选择导致退化、划分区间越界、大于交换后推进 i、递归区间错位、等于段重复递归、随机下标范围错;按划分指针、递归区间、重复处理复核。

概念解释

  • 划分指针。
  • 区间边界。
  • 重复口径。

原理流程

  1. 核对 pivot 与指针。
  2. 核对递归左右区间。
  3. 核对等于段处理。

代码 / 图示

partition → 递归 [l,p-1] [p+1,r]

常见误区

  • 误区:递归含 pivot 自身;正解:两侧排除基准。
  • 误区:Hoare 分界当 pivot 下标;正解:按分界切区间。

追问

  • Q:怎么自测划分? A:划分后基准左侧都 ≤、右侧都 ≥。
  • Q:随机下标越界? A:l + rand(r-l+1)。

02.5.2.2-017 快排复杂度怎么汇报?

一句话结论

平均 O(n log n),最坏 O(n²);随机化后期望 O(n log n);原地排序,递归栈平均 O(log n)、最坏 O(n);不稳定;快速选择平均 O(n)、最坏 O(n²)。

概念解释

  • 平均/最坏。
  • 栈空间。
  • 稳定性。

原理流程

  1. 标注划分均衡度。
  2. 标注递归深度。
  3. 分列时间空间。

代码 / 图示

快排:平均 O(n log n) / 最坏 O(n²) / 栈 O(log n)
快选:平均 O(n) / 最坏 O(n²)

常见误区

  • 误区:快排空间 O(1);正解:递归栈另计。
  • 误区:随机化后无最坏;正解:期望口径。

追问

  • Q:三路划分重复数据复杂度? A:等于段跳过,重复多时更接近线性。
  • Q:迭代快排空间? A:显式栈 O(log n) 平均。

02.5.2.2-018 随机化 pivot 为什么能保证期望性能?

一句话结论

随机基准使划分位置在期望意义上均匀,递归树期望高度 O(log n);最坏 O(n²) 仍存在但概率极低;期望复杂度是概率口径,不是确定性保证。

概念解释

  • 期望均匀。
  • 概率口径。
  • 最坏保留。

原理流程

  1. 随机选基准。
  2. 期望划分比例均衡。
  3. 递归树期望对数高。

代码 / 图示

随机 pivot → 期望 O(n log n)

常见误区

  • 误区:随机化后最坏不可能;正解:理论最坏仍 O(n²)。
  • 误区:每次随机重新播种;正解:随机源全局复用即可。

追问

  • Q:对抗性输入? A:随机化使预设退化失效。
  • Q:三数取中对比? A:确定性启发式,不保证期望。

02.5.2.2-019 快排变体有哪些常见追问?

一句话结论

为什么不稳定、最坏复杂度、pivot 策略、三路划分用途、与归并对比、快速选择复杂度、递归栈优化、小区间插入;回答围绕划分均衡、空间与稳定性。

概念解释

  • 性质追问。
  • 优化策略。
  • 选型对比。

原理流程

  1. 说划分模型。
  2. 报复杂度口径。
  3. 对比替代算法。

代码 / 图示

划分 → 均衡度 → 复杂度/稳定/空间

常见误区

  • 误区:追问时只答平均;正解:补最坏与空间栈。
  • 误区:说不清三路解决什么;正解:大量重复元素。

追问

  • Q:快速选择最坏怎么防? A:随机 pivot + 中位中位数算法(进阶)。
  • Q:快排能稳定化吗? A:额外空间分区可,代价 O(n)。

02.5.2.2-020 快排与三路划分常见变体有哪些?

一句话结论

手写快排 Lomuto/Hoare、随机化 pivot、三路划分颜色分类、快速选择第 K 大、小数组插入优化、短侧优先递归、迭代快排;主线是 partition 划分 + 单侧/双侧递归。

概念解释

  • 框架:分治划分。
  • 变体:划分方式与目标。
  • 工程优化。

原理流程

  1. 写 partition。
  2. 双侧排序或单侧选择。
  3. 叠加优化。

代码 / 图示

全排序:双侧递归
第 K:单侧收缩
重复:三路分区

常见误区

  • 误区:变体题脱离 partition 框架;正解:划分是核心。
  • 误区:快速选择误用全排序;正解:单侧收缩平均线性。

追问

  • Q:归并逆序对见哪页? A:02.5.2.3。
  • Q:堆排序与 Top-K 见哪页? A:02.5.2.4 与 02.3.2.4。