02.5.2.2 快排与三路划分
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序 / 02.5.2 排序算法与设计
02.5.2.2-001 快速排序的基本思想是什么?
一句话结论
分治:选 pivot 把数组划分为小于、等于、大于三部分,递归排序两侧;平均 O(n log n),原地,不稳定;核心是 partition 把基准放到最终位置。
概念解释
- 分治划分。
- pivot 定位。
- 两侧递归。
原理流程
- 选基准。
- 划分区间。
- 递归左右。
代码 / 图示
[< 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;返回基准下标。
概念解释
- 小于区边界。
- 遍历交换。
- 基准归位。
原理流程
- pivot = 末元素。
- j 遍历,小于则扩小于区。
- 基准换到分界。
代码 / 示例
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。
概念解释
- 双指针相向。
- 逆序对交换。
- 相遇分界。
原理流程
- 选基准。
- 左扫过小于,右扫过大于。
- 交换逆序对直到相遇。
代码 / 示例
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)。
概念解释
- 退化原因。
- 随机化。
- 三数取中。
原理流程
- 随机选下标交换到端点。
- 或取左中右中位数。
- 再划分。
代码 / 示例
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)。
概念解释
- 每层线性。
- 深度对数/线性。
- 乘积复杂度。
原理流程
- 划分 O(n)。
- 递归树深度。
- 层代价求和。
代码 / 图示
均衡: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 优化。
- 小规模切换。
- 重复处理。
原理流程
- 随机化基准。
- 短区间插入。
- 重复元素三路。
代码 / 图示
随机 pivot + 插入阈值 + 三路划分
常见误区
- 误区:优化后无最坏;正解:理论最坏仍 O(n²),概率极低。
- 误区:小区间用快排递归;正解:阈值下插入更省常数。
追问
- Q:插入阈值多少? A:常见 10 左右,具体按基准测试,待确认。
- Q:递归栈爆掉? A:先递归短侧,长侧循环迭代。
02.5.2.2-007 三路划分解决什么问题?
一句话结论
把区间分为 < pivot、== pivot、> pivot 三段;大量重复元素时等于段不再参与递归,避免重复元素导致的退化;荷兰国旗问题即三路划分。
概念解释
- 三段分区。
- 等于段跳过。
- 重复友好。
原理流程
- 维护 lt、gt、i 三指针。
- 小于换 lt 后扩,大于换 gt 后扩。
- 等于跳过。
代码 / 示例
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/三路都存在跨距交换;需要稳定排序时选归并。
概念解释
- 跨距交换。
- 等值次序。
- 稳定性破坏。
原理流程
- 相等元素被不同交换移动。
- 相对次序可能反转。
- 判定不稳定。
代码 / 图示
等值元素跨距交换 → 次序改变
常见误区
- 误区:等于 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);辅助数组不需要。
概念解释
- 栈深 = 树高。
- 短侧优先。
- 迭代长侧。
原理流程
- 划分得两侧长度。
- 先递归短侧。
- 长侧改循环继续。
代码 / 图示
先排短区间,长区间循环接管
常见误区
- 误区:两侧都递归导致深链爆栈;正解:短侧优先迭代长侧。
- 误区:快排 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 小。
概念解释
- 只排一侧。
- 位置比较。
- 平均线性。
原理流程
- partition 得基准下标。
- 比较目标位置。
- 命中返回,否则单侧递归。
代码 / 示例
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) 迭代。
概念解释
- 单侧收缩。
- 几何级数。
- 期望线性。
原理流程
- 划分 O(m)。
- 期望剩余 αm。
- 求和 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) 额外空间;内存充足且要稳定选归并,空间敏感选快排。
概念解释
- 空间。
- 稳定性。
- 最坏口径。
原理流程
- 对比空间与稳定。
- 对比最坏复杂度。
- 按约束选型。
代码 / 图示
快排:原地 不稳 平均快
归并:O(n) 稳 最坏稳
常见误区
- 误区:快排比归并快所以总选快排;正解:稳定/链表场景归并更合适。
- 误区:归并原地可做;正解:标准归并需辅助数组。
追问
- Q:链表排序用哪个? A:归并,指针合并无需额外节点数组。
- Q:外部排序? A:归并分治,见 02.5.2.4。
02.5.2.2-013 小区间为什么切换插入排序?
一句话结论
快排递归到小规模区间时,递归开销与常数超过插入排序;阈值以下改插入,减少递归调用与划分常数;不改变渐近复杂度,优化实际运行。
概念解释
- 小规模常数。
- 递归开销。
- 混合优化。
原理流程
- 区间长度低于阈值。
- 改插入排序。
- 不再递归划分。
代码 / 示例
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) 空间;是三路划分的直接应用。
概念解释
- 三色分区。
- 单趟扫描。
- 边界指针。
原理流程
- lt=0, gt=n-1, i=0。
- 0 换 lt,2 换 gt,1 跳过。
- 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] / 升序 / 逆序 / 全相等
常见误区
- 误区:全相等用普通两路划分退化;正解:三路跳过等于段。
- 误区:递归终止
l<r写错;正解:l>=r返回。
追问
- Q:两元素划分? A:一次 partition 就位。
- Q:极值比较溢出? A:避免减法比较。
02.5.2.2-016 快排常见错误有哪些?
一句话结论
pivot 选择导致退化、划分区间越界、大于交换后推进 i、递归区间错位、等于段重复递归、随机下标范围错;按划分指针、递归区间、重复处理复核。
概念解释
- 划分指针。
- 区间边界。
- 重复口径。
原理流程
- 核对 pivot 与指针。
- 核对递归左右区间。
- 核对等于段处理。
代码 / 图示
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²)。
概念解释
- 平均/最坏。
- 栈空间。
- 稳定性。
原理流程
- 标注划分均衡度。
- 标注递归深度。
- 分列时间空间。
代码 / 图示
快排:平均 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²) 仍存在但概率极低;期望复杂度是概率口径,不是确定性保证。
概念解释
- 期望均匀。
- 概率口径。
- 最坏保留。
原理流程
- 随机选基准。
- 期望划分比例均衡。
- 递归树期望对数高。
代码 / 图示
随机 pivot → 期望 O(n log n)
常见误区
- 误区:随机化后最坏不可能;正解:理论最坏仍 O(n²)。
- 误区:每次随机重新播种;正解:随机源全局复用即可。
追问
- Q:对抗性输入? A:随机化使预设退化失效。
- Q:三数取中对比? A:确定性启发式,不保证期望。
02.5.2.2-019 快排变体有哪些常见追问?
一句话结论
为什么不稳定、最坏复杂度、pivot 策略、三路划分用途、与归并对比、快速选择复杂度、递归栈优化、小区间插入;回答围绕划分均衡、空间与稳定性。
概念解释
- 性质追问。
- 优化策略。
- 选型对比。
原理流程
- 说划分模型。
- 报复杂度口径。
- 对比替代算法。
代码 / 图示
划分 → 均衡度 → 复杂度/稳定/空间
常见误区
- 误区:追问时只答平均;正解:补最坏与空间栈。
- 误区:说不清三路解决什么;正解:大量重复元素。
追问
- Q:快速选择最坏怎么防? A:随机 pivot + 中位中位数算法(进阶)。
- Q:快排能稳定化吗? A:额外空间分区可,代价 O(n)。
02.5.2.2-020 快排与三路划分常见变体有哪些?
一句话结论
手写快排 Lomuto/Hoare、随机化 pivot、三路划分颜色分类、快速选择第 K 大、小数组插入优化、短侧优先递归、迭代快排;主线是 partition 划分 + 单侧/双侧递归。
概念解释
- 框架:分治划分。
- 变体:划分方式与目标。
- 工程优化。
原理流程
- 写 partition。
- 双侧排序或单侧选择。
- 叠加优化。
代码 / 图示
全排序:双侧递归
第 K:单侧收缩
重复:三路分区
常见误区
- 误区:变体题脱离 partition 框架;正解:划分是核心。
- 误区:快速选择误用全排序;正解:单侧收缩平均线性。
追问
- Q:归并逆序对见哪页? A:02.5.2.3。
- Q:堆排序与 Top-K 见哪页? A:02.5.2.4 与 02.3.2.4。