快速排序江湖人称“快排”是工程中最常用的排序算法——Java的Arrays.sort()、C 的std::sort都依赖它。它平均 O(nlogn)原地排序常数小看似完美。「但 LeetCode 912 这道题专门用来打脸“伪快排”。」你写了个经典快排选第一个元素做 pivot → 已排序数组直接退化成 O(n²)超时。你加了随机化但遇到全重复元素 → 二路切分仍然递归深度爆炸超时。你终于写出了「随机化 三路切分」才稳稳 AC。今天我们就从“必挂”写到“必过”把快排的底裤扒个干净。顺便为后面Day13的“快速选择”打好地基。 题目速览30 秒读懂给你一个整数数组nums将其升序排列。「示例」[5,2,3,1]→[1,2,3,5]「示例」[5,1,1,2,0,0]→[0,0,1,1,2,5]「约束」长度 ≤ 5×10⁴数值范围±5×10⁴。暴力O(n²)必挂必须写出高效的O(nlogn)排序。 核心思路分治 分区pivot 归位是关键暴力慢在哪选择排序、插入排序都是O(n²) —— 5万长度 ≈ 25亿次交换直接超时。快排的“分治”哲学归并排序是“先拆再合”快排反过来「先分区partition再递归两侧」。分区做什么选一个基准值pivot把数组排成三块[小于pivot] [pivot] [大于pivot]。这一步做完pivot就落在了它最终的位置上。然后对左右两块分别递归直到每块只剩一个元素。「分区怎么写」两种主流写法「挖坑法」把pivot挖出来左右指针交替填坑。适合白板讲解。「交换法双指针」维护一个“小于区”的边界遍历数组把小于pivot的元素交换到边界内。代码更短工程常用。为什么朴素快排会退化如果每次都选到最大或最小值做pivot分区极度不平衡递归深度变成n → O(n²)。典型触发场景「已排序数组 固定选首元素」「全重复数组 二路切分」因为所有元素相等pivot归位后两边规模几乎不变。「两剂猛药」「随机化 pivot」随机选一个位置与首元素交换让“最坏输入”变成小概率事件期望O(nlogn)。「三路切分」把数组分成三段[pivot] [pivot] [pivot]。全重复数组时中间那一段一次性“吃掉”所有元素递归深度骤降。️ 图解算法二路 vs 三路二路切分交换法演示nums [5, 2, 3, 1]随机选pivot 3与首元素交换后数组变为[3, 2, 5, 1]步骤数组状态lti动作初始[3, 2, 5, 1]01pivot3i 从 1 开始i1[3, 2, 5, 1]0→11→2nums[1]23交换 nums[1]↔nums[0]lt1i2[2, 3, 5, 1]12→3nums[2]5≥3跳过i3[2, 3, 5, 1]1→23→4nums[3]13交换 nums[3]↔nums[1]lt2归位[2, 1, 5, 3]2—交换 nums[0]↔nums[lt-1]pivot 3 落到索引 2一轮后[2,1] 3 [5]左侧递归排[2,1]右侧单元素结束。三路切分演示专治重复元素nums [2,2,1,2]pivot 2iltgt数组状态动作初始03[2,2,1,2]lt0, gt3, i0i003[2,2,1,2]nums[0]pivotii103[2,2,1,2]nums[1]pivotii203[2,2,1,2]nums[2]1pivot交换 nums[2]↔nums[0]lt1,ii2(继续)13[1,2,2,2]i2, nums[2]pivotii313[1,2,2,2]nums[3]pivoti结束13[1,2,2,2]lt1, gt3 → 中间三个 2 全部归位一趟分区后[1] [2,2,2] []中间段无需再递归。重复元素越多收益越大。 代码实现Python JavaAC 必过版Python 版三路切分 随机化 尾递归优化importrandomclassSolution:defsortArray(self, nums: List[int])- List[int]:self.quick_sort(nums,0, len(nums) -1)returnnumsdefquick_sort(self, nums, lo, hi):whilelo hi:# 尾递归优化大侧用循环只递归小侧# 随机选 pivotpivot nums[random.randint(lo, hi)]lt, i, gt lo, lo, hiwhilei gt:ifnums[i] pivot:nums[lt], nums[i] nums[i], nums[lt]lt 1i 1elifnums[i] pivot:nums[i], nums[gt] nums[gt], nums[i]gt -1else:i 1# 先递归较小的区间较大区间用循环iflt - lo hi - gt:self.quick_sort(nums, lo, lt -1)lo gt 1else:self.quick_sort(nums, gt 1, hi)hi lt -1Java 版二路切分 随机化更易理解classSolution{publicint[] sortArray(int[] nums) {quickSort(nums,0, nums.length -1);returnnums;}privatevoidquickSort(int[] nums,intlo,inthi){if(lo hi)return;intp partition(nums, lo, hi);quickSort(nums, lo, p -1);quickSort(nums, p 1, hi);}privateintpartition(int[] nums,intlo,inthi){// 随机 pivot 换到 lointr lo (int)(Math.random() * (hi - lo 1));swap(nums, lo, r);intpivot nums[lo];intlt lo 1;for(inti lo 1; i hi; i) {if(nums[i] pivot) {swap(nums, i, lt);}}swap(nums, lo, lt -1);returnlt -1;}privatevoidswap(int[] a,inti,intj){intt a[i]; a[i] a[j]; a[j] t;}}⚠️「关键细节必看」随机化pivot是防超时的第一道防线。三路切分中nums[i] pivot分支交换后「i 不前进」因为从gt换过来的元素还没检查。尾递归优化Python 版保证递归栈深度 ≤ O(log n)避免最坏空间。⏱️ 复杂度分析面试必问「时间」平均 / 期望「O(nlogn)」随机化保证最坏O(n²)但概率极低三路切分在重复元素多时接近O(n)「空间」原地排序递归栈平均O(logn)最坏O(n)尾递归优化后稳定O(logn) 举一反三4 道高频变种题一套框架通吃题目变化点应对策略「LC.215 数组中的第K个最大元素」只需部分有序求第K大快速选择只递归一侧期望O(n)「LC.75 颜色分类」只含 0/1/2一次排序三路切分荷兰国旗O(n)「LC.912 其他解法」归并排序、堆排序亦可对比不同分治策略Day9详解归并「LC.剑指 Offer 51 逆序对」统计逆序对个数归并排序天然适合快排不行 面试追问模拟提前准备惊艳全场「Q1快排为什么不稳定」因为分区时相等元素的相对顺序可能被交换破坏。例如[3a, 3b, 2]选pivot2后3a和3b可能互换位置。「Q2什么时候会退化成O(n²)怎么避免」当每次pivot都选到极值时有序数组 固定选首/尾或全重复数组 二路切分。避免方法①随机化 pivot②三路切分处理重复元素。「Q3还有哪些优化技巧」小区间切换插入排序长度 16时三数取中median-of-three选pivot双轴快排Java的DualPivotQuicksort用两个 pivot分成三区尾递归优化控制栈深度 实战小技巧刷题党必备「口诀」随机pivot防极端三路切分治重复尾递归省栈空间。「模板」凡是手写快排默认加随机化遇到大量重复元素必须三路切分。「验证」用有序数组、逆序数组、全相同数组测试确保不超时。 实际应用场景不止是刷题「语言标准库排序」JavaArrays.sort(int[])、Cstd::sortintrosort是快排 堆排序混合「数据库内存排序」查询结果排序的底层实现「大数据框架」Spark、Hadoop的shuffle阶段排序「Top-K问题」快速选择是快排的直接衍生 今日思考题如果数组元素是自定义对象比如按年龄排序快排还稳定吗如何让它稳定「提示」快排本身不稳定但可以改造为稳定版本如使用额外数组但那样会牺牲原地性。你能写一个“稳定快排”吗