面试里有个残酷的事实快排你“懂”和你能“写出来”是两件事。懂的人能跟你聊半天复杂度真到白板前往往卡在三个地方哨兵指针的初始位置差一位内外层循环要不要加等号递归边界是p-1还是p这三处任意一个写错10分钟就交代了。而且快排的partition至少有三种主流写法挖坑法、Lomuto、Hoare它们切分约定、返回值语义、递归边界各不相同混用必炸。 题目速览 LeetCode 91230秒读懂给你一个整数数组nums升序排列。示例[5,2,3,1]→[1,2,3,5]示例[5,1,1,2,0,0]→[0,0,1,1,2,5]约束n ≤ 5e4数值 ±5e4。今天的白板合约面试官真正的要求要求说明手写不能调库面试官要看你有没有把结构装进肌肉记忆10分钟内完成需要固定模板 口诀不是现场推导三种partition至少写对一种追问“还有别的写法吗”是标配能答出复杂度、稳定性、退化场景拉开差距的地方通过有序数组和全重复数组这两档是朴素快排的催命符 白板答题节奏别一上来就写代码面试官最想看的不是代码是你的沟通顺序。固定按这五步走1. 说清strategy30秒我用分治。三步分——选pivot一轮partition 把它放到最终位置治——对左右两段递归合——不用合pivot 已归位。2. 手推复杂度30秒理想情况每轮均分树高logn每层O(n)所以O(nlogn)。最坏是每次选到极值pivot退化成O(n²)——我会用随机化把这件事变成概率事件。3. 写代码5分钟挑你最有把握的一种partition默写到一字不错别贪多。4. 主动说退化防护30秒随机化治有序数组三路切分治重复元素。5. 主动迎接追问1分钟它不是稳定排序它是原地的空间只有递归栈O(logn)。 三种 partition 横向对比核心写法pivot取哪指针怎么走返回值语义递归区间特点① 挖坑法a[lo]挖出来左右交替赋值填坑pivot最终下标[lo,p-1][p1,hi]国内教材最爱最好讲② Lomutoa[hi]必须在末位单向扫描lt守小于区pivot最终下标[lo,p-1][p1,hi]代码最短、最不易写错推荐默写③ Hoare常取中位双向交错交换不保证pivot归位j是分界线[lo,p][p1,hi]交换次数最少边界最易错⚠️ 第一号大坑Hoare的返回值不能当“pivot已就位”挖坑法和Lomuto返回p后p位置就是pivot天然不属于任何一侧递归区间是[lo,p-1]和[p1,hi]。Hoare只保证“j及其左边都 ≤ j1 及其右边”pivot自己都不一定停在j上。所以必须递归[lo,p]和[p1,hi]。实测写错会怎样——Hoare配成[lo,p-1]/[p1,hi]输入 [3,2,6,0,1,3,5,1,4,3,1,2] 输出 [0,1,1,2,2,3,1,3,3,4,5,6] ← 第6位的1掉队了p位置的元素被两侧递归同时跳过永远没被处理。⚠️ 第二号大坑Hoare内层必须用do-while如果写成while (a[i] pivot) i;遇到大量等于pivot的元素时两个指针一步都走不动——死循环。实测[2,2,2,2]while版跑了50轮还在原地打转。正解do-while先移动再判断。⚠️ 第三号大坑Lomuto两套写法不能混用末位版pivot a[hi]扫[lo, hi-1]最后swap(lt, hi)return lt首位版pivot a[lo]扫[lo1, hi]最后swap(lo, lt-1)return lt-1混用后果实测[5,3,8,4,2,7,1,6] → [7,3,4,2,1,5,8,6]左侧出现7 5 → 分区错误 [4,1,3,2] → 直接IndexError结论背一套别混。推荐「末位版Lomuto」。️ 图解算法同一数组跑三种写法第一轮a [5, 3, 8, 4, 2, 7, 1, 6]① 挖坑法pivot a[0] 5步动作数组状态1从右找 5j6值1填左坑[1, 3, 8, 4, 2, 7, 1, 6]2从左找 5i2值8填右坑[1, 3, 8, 4, 2, 7, 8, 6]3从右找 5j4值2填左坑[1, 3, 2, 4, 2, 7, 8, 6]4i追上j循环结束同上归位pivot放进a[4][1, 3, 2, 4,5, 7, 8, 6]return 4要点全程是赋值不是交换。左边[1,3,2,4]全 5右边[7,8,6]全 5 ✅② Lomuto末位版pivot a[7] 6ia[i]比较动作lt数组05 6swap无变化lt1[5, 3, 8, 4, 2, 7, 1, 6]13 6swap无变化lt2同上28≥ 6跳过2同上34 6swap(3,2)lt3[5, 3, 4, 8, 2, 7, 1, 6]42 6swap(4,3)lt4[5, 3, 4, 2, 8, 7, 1, 6]57≥ 6跳过4同上61 6swap(6,4)lt5[5, 3, 4, 2, 1, 7, 8, 6]归位——swap(5,7)—[5, 3, 4, 2, 1,6, 8, 7]return5要点不变式一句话——lt始终指向“小于区的下一个待填位置”[lo, lt-1]全部 pivot。③ Hoarepivot a[3] 4轮ij判断动作数组106i j交换[1, 3, 8, 4, 2, 7, 5, 6]224i j交换[1, 3, 2, 4, 8, 7, 5, 6]333i ≥ jreturn j3同上要点左段[1,3,2,4]全 ≤ 右段[8,7,5,6]✅但4和8的相对位置还没定论——Hoare从不保证pivot就在j位置。 代码实现Python JavaPython版importrandomfromtypingimportListclassSolution:defsortArray(self,nums:List[int])-List[int]:iflen(nums)1:self._quick(nums,0,len(nums)-1)returnnums# 统一递归驱动尾递归优化栈深度O(logn)def_quick(self,a,lo,hi):whilelohi:pself._part_lomuto(a,lo,hi)# 换成哪个都行注意配套递归区间ifp-lohi-p:# 先压较小的一侧self._quick(a,lo,p-1)lop1else:self._quick(a,p1,hi)hip-1# ① 挖坑法def_part_hole(self,a,lo,hi):pivota[lo]i,jlo,hiwhileij:whileijanda[j]pivot:j-1a[i]a[j]whileijanda[i]pivot:i1a[j]a[i]a[i]pivotreturni# ② Lomuto末位版推荐默写def_part_lomuto(self,a,lo,hi):rrandom.randint(lo,hi)# 随机化pivota[r],a[hi]a[hi],a[r]pivota[hi]ltlo# [lo, lt-1]全都 pivotforiinrange(lo,hi):ifa[i]pivot:a[i],a[lt]a[lt],a[i]lt1a[lt],a[hi]a[hi],a[lt]returnlt# ③ Hoaredef_part_hoare(self,a,lo,hi):pivota[lo(hi-lo)//2]# 必须取数组真实值i,jlo-1,hi1whileTrue:i1whilea[i]pivot:i1# do-while语义j-1whilea[j]pivot:j-1ifij:returnj# 返回j不是ia[i],a[j]a[j],a[i]Java版importjava.util.concurrent.ThreadLocalRandom;classSolution{publicint[]sortArray(int[]nums){if(nums.length1)quick(nums,0,nums.length-1);returnnums;}privatevoidquick(int[]a,intlo,inthi){while(lohi){if(hi-lo12){insertionSort(a,lo,hi);return;}intppartLomuto(a,lo,hi);if(p-lohi-p){quick(a,lo,p-1);lop1;}else{quick(a,p1,hi);hip-1;}}}privateintpartLomuto(int[]a,intlo,inthi){intrloThreadLocalRandom.current().nextInt(hi-lo1);swap(a,r,hi);intpivota[hi];intltlo;for(intilo;ihi;i){if(a[i]pivot)swap(a,i,lt);}swap(a,lt,hi);returnlt;}privatevoidinsertionSort(int[]a,intlo,inthi){for(intilo1;ihi;i){intva[i],ji-1;while(jloa[j]v){a[j1]a[j];j--;}a[j1]v;}}privatevoidswap(int[]a,inti,intj){intta[i];a[i]a[j];a[j]t;}}⚠️防坑提醒Hoare的pivot必须取自数组实际元素不能取计算值。尾递归优化把栈从最坏O(n) 压到O(logn)。Hoare驱动必须[lo,p]/[p1,hi]写成p-1就是漏排元素的bug。⭐ 能默写的记忆模板项内容口诀“取末、扫前、小于就换、最后归位”Lomuto末位版骨架四行pivota[hi]→for i in [lo,hi)→if a[i]pivot: swap(i, lt)→swap(lt,hi); return lt递归三行while lohi:→ppartition(lo,hi)→quick(lo,p-1); quick(p1,hi)随机化一行swap(a, rand(lo,hi), hi)—— 治有序数组不加必超时复杂度树高logn × 每层O(n) O(nlogn)最坏O(n²)空间O(logn) 栈两个主动交代①不稳定②原地空间只有递归栈换Hoare改两处return j递归[lo,p]和[p1,hi]⏱️ 复杂度分析面试必问场景时间说明平均/期望O(nlogn)均匀partition树高logn最坏O(n²)每次都选到极值pivot有序数组 固定选首/尾重复元素二路退化需三路切分Hoare把等值分两侧反而更安全空间原地交换只有递归栈。平均O(logn)尾递归优化后强制压到O(logn)。三种写法常数差异Hoare 交换次数最少约为Lomuto的1/3。但从“10分钟能不能写对”角度Lomuto完胜。 举一反三5道相关变体题题目与快排的关系LC.215 第K大元素partition后只递归一侧 →快速选择O(n)LC.75 颜色分类三路切分的裸题一次O(n)排完LC.324 摆动排序II三路切分思想的变体剑指 Offer 40 最小的k个数partition-only-one-sideLC.912今天裸快排 反退火测试 面试追问模拟提前准备惊艳全场Q1Hoare和Lomuto谁快常数上Hoar 更快交换次数约为Lomuto的1/3重复元素多时切分更均衡。Hoare的返回值语义和递归边界是著名易错点。面试白板优先选Lomuto写对 写快想秀再上Hoare并主动说清“为什么递归区间是[lo,p]”。Q2为什么Hoare边界容易写错因为它的返回值j不是“pivot的最终位置”而是“左半区最右元素的下标”。这与挖坑法/Lomuto的返回值语义完全不同。人的肌肉记忆一旦形成“返回值 pivot位置 → 跳开它递归”p-1就顺手写下去了。Q3什么是introsortCstd::sort的实际实现。三层兜底主干快排递归深度超过2·log₂ n切换堆排序把最坏压到 O(nlogn)区间 16切插入排序。运行时监控递归深度发现退化就换算法。Q4Java的Arrays.sort内部是什么基本类型DualPivotQuicksort双轴快排两个pivot切三段不稳定但原地省内存。对象数组TimSort归并插入因为对象排序必须稳定。Q5什么时候不该用快排① 要稳定 → 归并/TimSort② 栈空间极度受限 → 堆排序③ 数据是外存/链表结构 → 归并。 实战小技巧刷题党必备口诀取末、扫前、小于就换、最后归位。模板Lomuto末位版 随机化 尾递归优化三件套默写。防坑Hoare用do-while、return j、递归[lo,p]。 实际应用场景不止是刷题所有语言通用排序函数Java双轴快排、C introsort数据库内存排序查询结果排序大数据shuffle内排Spark/Hadoop快速选择衍生Top-K问题 今日思考题把_part_hoare配错递归边界后跑[3,2,6,0,1,3,5,1,4,3,1,2]看看错误输出是不是[0,1,1,2,2,3,1,3,3,4,5,6]你面试时被要求手撕过哪种partition
面试里有个残酷的事实快排你“懂”和你能“写出来”是两件事。懂的人能跟你聊半天复杂度真到白板前往往卡在三个地方哨兵指针的初始位置差一位内外层循环要不要加等号递归边界是p-1还是p这三处任意一个写错10分钟就交代了。而且快排的partition至少有三种主流写法挖坑法、Lomuto、Hoare它们切分约定、返回值语义、递归边界各不相同混用必炸。 题目速览 LeetCode 91230秒读懂给你一个整数数组nums升序排列。示例[5,2,3,1]→[1,2,3,5]示例[5,1,1,2,0,0]→[0,0,1,1,2,5]约束n ≤ 5e4数值 ±5e4。今天的白板合约面试官真正的要求要求说明手写不能调库面试官要看你有没有把结构装进肌肉记忆10分钟内完成需要固定模板 口诀不是现场推导三种partition至少写对一种追问“还有别的写法吗”是标配能答出复杂度、稳定性、退化场景拉开差距的地方通过有序数组和全重复数组这两档是朴素快排的催命符 白板答题节奏别一上来就写代码面试官最想看的不是代码是你的沟通顺序。固定按这五步走1. 说清strategy30秒我用分治。三步分——选pivot一轮partition 把它放到最终位置治——对左右两段递归合——不用合pivot 已归位。2. 手推复杂度30秒理想情况每轮均分树高logn每层O(n)所以O(nlogn)。最坏是每次选到极值pivot退化成O(n²)——我会用随机化把这件事变成概率事件。3. 写代码5分钟挑你最有把握的一种partition默写到一字不错别贪多。4. 主动说退化防护30秒随机化治有序数组三路切分治重复元素。5. 主动迎接追问1分钟它不是稳定排序它是原地的空间只有递归栈O(logn)。 三种 partition 横向对比核心写法pivot取哪指针怎么走返回值语义递归区间特点① 挖坑法a[lo]挖出来左右交替赋值填坑pivot最终下标[lo,p-1][p1,hi]国内教材最爱最好讲② Lomutoa[hi]必须在末位单向扫描lt守小于区pivot最终下标[lo,p-1][p1,hi]代码最短、最不易写错推荐默写③ Hoare常取中位双向交错交换不保证pivot归位j是分界线[lo,p][p1,hi]交换次数最少边界最易错⚠️ 第一号大坑Hoare的返回值不能当“pivot已就位”挖坑法和Lomuto返回p后p位置就是pivot天然不属于任何一侧递归区间是[lo,p-1]和[p1,hi]。Hoare只保证“j及其左边都 ≤ j1 及其右边”pivot自己都不一定停在j上。所以必须递归[lo,p]和[p1,hi]。实测写错会怎样——Hoare配成[lo,p-1]/[p1,hi]输入 [3,2,6,0,1,3,5,1,4,3,1,2] 输出 [0,1,1,2,2,3,1,3,3,4,5,6] ← 第6位的1掉队了p位置的元素被两侧递归同时跳过永远没被处理。⚠️ 第二号大坑Hoare内层必须用do-while如果写成while (a[i] pivot) i;遇到大量等于pivot的元素时两个指针一步都走不动——死循环。实测[2,2,2,2]while版跑了50轮还在原地打转。正解do-while先移动再判断。⚠️ 第三号大坑Lomuto两套写法不能混用末位版pivot a[hi]扫[lo, hi-1]最后swap(lt, hi)return lt首位版pivot a[lo]扫[lo1, hi]最后swap(lo, lt-1)return lt-1混用后果实测[5,3,8,4,2,7,1,6] → [7,3,4,2,1,5,8,6]左侧出现7 5 → 分区错误 [4,1,3,2] → 直接IndexError结论背一套别混。推荐「末位版Lomuto」。️ 图解算法同一数组跑三种写法第一轮a [5, 3, 8, 4, 2, 7, 1, 6]① 挖坑法pivot a[0] 5步动作数组状态1从右找 5j6值1填左坑[1, 3, 8, 4, 2, 7, 1, 6]2从左找 5i2值8填右坑[1, 3, 8, 4, 2, 7, 8, 6]3从右找 5j4值2填左坑[1, 3, 2, 4, 2, 7, 8, 6]4i追上j循环结束同上归位pivot放进a[4][1, 3, 2, 4,5, 7, 8, 6]return 4要点全程是赋值不是交换。左边[1,3,2,4]全 5右边[7,8,6]全 5 ✅② Lomuto末位版pivot a[7] 6ia[i]比较动作lt数组05 6swap无变化lt1[5, 3, 8, 4, 2, 7, 1, 6]13 6swap无变化lt2同上28≥ 6跳过2同上34 6swap(3,2)lt3[5, 3, 4, 8, 2, 7, 1, 6]42 6swap(4,3)lt4[5, 3, 4, 2, 8, 7, 1, 6]57≥ 6跳过4同上61 6swap(6,4)lt5[5, 3, 4, 2, 1, 7, 8, 6]归位——swap(5,7)—[5, 3, 4, 2, 1,6, 8, 7]return5要点不变式一句话——lt始终指向“小于区的下一个待填位置”[lo, lt-1]全部 pivot。③ Hoarepivot a[3] 4轮ij判断动作数组106i j交换[1, 3, 8, 4, 2, 7, 5, 6]224i j交换[1, 3, 2, 4, 8, 7, 5, 6]333i ≥ jreturn j3同上要点左段[1,3,2,4]全 ≤ 右段[8,7,5,6]✅但4和8的相对位置还没定论——Hoare从不保证pivot就在j位置。 代码实现Python JavaPython版importrandomfromtypingimportListclassSolution:defsortArray(self,nums:List[int])-List[int]:iflen(nums)1:self._quick(nums,0,len(nums)-1)returnnums# 统一递归驱动尾递归优化栈深度O(logn)def_quick(self,a,lo,hi):whilelohi:pself._part_lomuto(a,lo,hi)# 换成哪个都行注意配套递归区间ifp-lohi-p:# 先压较小的一侧self._quick(a,lo,p-1)lop1else:self._quick(a,p1,hi)hip-1# ① 挖坑法def_part_hole(self,a,lo,hi):pivota[lo]i,jlo,hiwhileij:whileijanda[j]pivot:j-1a[i]a[j]whileijanda[i]pivot:i1a[j]a[i]a[i]pivotreturni# ② Lomuto末位版推荐默写def_part_lomuto(self,a,lo,hi):rrandom.randint(lo,hi)# 随机化pivota[r],a[hi]a[hi],a[r]pivota[hi]ltlo# [lo, lt-1]全都 pivotforiinrange(lo,hi):ifa[i]pivot:a[i],a[lt]a[lt],a[i]lt1a[lt],a[hi]a[hi],a[lt]returnlt# ③ Hoaredef_part_hoare(self,a,lo,hi):pivota[lo(hi-lo)//2]# 必须取数组真实值i,jlo-1,hi1whileTrue:i1whilea[i]pivot:i1# do-while语义j-1whilea[j]pivot:j-1ifij:returnj# 返回j不是ia[i],a[j]a[j],a[i]Java版importjava.util.concurrent.ThreadLocalRandom;classSolution{publicint[]sortArray(int[]nums){if(nums.length1)quick(nums,0,nums.length-1);returnnums;}privatevoidquick(int[]a,intlo,inthi){while(lohi){if(hi-lo12){insertionSort(a,lo,hi);return;}intppartLomuto(a,lo,hi);if(p-lohi-p){quick(a,lo,p-1);lop1;}else{quick(a,p1,hi);hip-1;}}}privateintpartLomuto(int[]a,intlo,inthi){intrloThreadLocalRandom.current().nextInt(hi-lo1);swap(a,r,hi);intpivota[hi];intltlo;for(intilo;ihi;i){if(a[i]pivot)swap(a,i,lt);}swap(a,lt,hi);returnlt;}privatevoidinsertionSort(int[]a,intlo,inthi){for(intilo1;ihi;i){intva[i],ji-1;while(jloa[j]v){a[j1]a[j];j--;}a[j1]v;}}privatevoidswap(int[]a,inti,intj){intta[i];a[i]a[j];a[j]t;}}⚠️防坑提醒Hoare的pivot必须取自数组实际元素不能取计算值。尾递归优化把栈从最坏O(n) 压到O(logn)。Hoare驱动必须[lo,p]/[p1,hi]写成p-1就是漏排元素的bug。⭐ 能默写的记忆模板项内容口诀“取末、扫前、小于就换、最后归位”Lomuto末位版骨架四行pivota[hi]→for i in [lo,hi)→if a[i]pivot: swap(i, lt)→swap(lt,hi); return lt递归三行while lohi:→ppartition(lo,hi)→quick(lo,p-1); quick(p1,hi)随机化一行swap(a, rand(lo,hi), hi)—— 治有序数组不加必超时复杂度树高logn × 每层O(n) O(nlogn)最坏O(n²)空间O(logn) 栈两个主动交代①不稳定②原地空间只有递归栈换Hoare改两处return j递归[lo,p]和[p1,hi]⏱️ 复杂度分析面试必问场景时间说明平均/期望O(nlogn)均匀partition树高logn最坏O(n²)每次都选到极值pivot有序数组 固定选首/尾重复元素二路退化需三路切分Hoare把等值分两侧反而更安全空间原地交换只有递归栈。平均O(logn)尾递归优化后强制压到O(logn)。三种写法常数差异Hoare 交换次数最少约为Lomuto的1/3。但从“10分钟能不能写对”角度Lomuto完胜。 举一反三5道相关变体题题目与快排的关系LC.215 第K大元素partition后只递归一侧 →快速选择O(n)LC.75 颜色分类三路切分的裸题一次O(n)排完LC.324 摆动排序II三路切分思想的变体剑指 Offer 40 最小的k个数partition-only-one-sideLC.912今天裸快排 反退火测试 面试追问模拟提前准备惊艳全场Q1Hoare和Lomuto谁快常数上Hoar 更快交换次数约为Lomuto的1/3重复元素多时切分更均衡。Hoare的返回值语义和递归边界是著名易错点。面试白板优先选Lomuto写对 写快想秀再上Hoare并主动说清“为什么递归区间是[lo,p]”。Q2为什么Hoare边界容易写错因为它的返回值j不是“pivot的最终位置”而是“左半区最右元素的下标”。这与挖坑法/Lomuto的返回值语义完全不同。人的肌肉记忆一旦形成“返回值 pivot位置 → 跳开它递归”p-1就顺手写下去了。Q3什么是introsortCstd::sort的实际实现。三层兜底主干快排递归深度超过2·log₂ n切换堆排序把最坏压到 O(nlogn)区间 16切插入排序。运行时监控递归深度发现退化就换算法。Q4Java的Arrays.sort内部是什么基本类型DualPivotQuicksort双轴快排两个pivot切三段不稳定但原地省内存。对象数组TimSort归并插入因为对象排序必须稳定。Q5什么时候不该用快排① 要稳定 → 归并/TimSort② 栈空间极度受限 → 堆排序③ 数据是外存/链表结构 → 归并。 实战小技巧刷题党必备口诀取末、扫前、小于就换、最后归位。模板Lomuto末位版 随机化 尾递归优化三件套默写。防坑Hoare用do-while、return j、递归[lo,p]。 实际应用场景不止是刷题所有语言通用排序函数Java双轴快排、C introsort数据库内存排序查询结果排序大数据shuffle内排Spark/Hadoop快速选择衍生Top-K问题 今日思考题把_part_hoare配错递归边界后跑[3,2,6,0,1,3,5,1,4,3,1,2]看看错误输出是不是[0,1,1,2,2,3,1,3,3,4,5,6]你面试时被要求手撕过哪种partition
