知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 01 - 快速排序 ## 题目(LeetCode 912) 给你一个整数数组 `nums`,请你将该数组升序排列。 ``` 输入:nums = [5, 2, 3, 1] 输出:[1, 2, 3, 5] ``` ## 大白话理解 快排的核心就一句话: > 随便挑一个数当 **基准(pivot)**,把比它小的扔左边,比它大的扔右边,然后对左右两边递归做同样的事。 类比:一堆人按身高排队,随便找个"中间高矮"的人当参照,比他矮的站左边,比他高的站右边。再对左右两队分别做同样的事,最后整个队伍就有序了。 ``` [5, 2, 3, 1] 挑 3 当基准 ↓ [2, 1] 3 [5] 比 3 小的左边,比 3 大的右边 ↓ 递归 ↓ 只有一个,不用排 [1] 2 挑 2 当基准 ↓ [] 1 [] 2 [] 3 [5] 合并 → [1, 2, 3, 5] ``` ## 核心操作:分区(partition) 分区是快排的灵魂。给定一个区间 `[left, right]`,选一个基准 `pivot`,把数组变成: ``` [ 比 pivot 小的 ] pivot [ 比 pivot 大的 ] ``` 然后返回 pivot 的最终位置。 ### Lomuto 分区(单指针,简单好写) ``` 思路:用一个 i 指针记录"小于 pivot 的区域"的右边界, j 从左扫到右,遇到小于 pivot 的就换到 i 的位置。 nums = [5, 2, 3, 1, 4],选最后一个 4 当 pivot 初始:i = -1(左边区域为空) j 从 0 开始扫 j=0, nums[0]=5 > 4,不动 j=1, nums[1]=2 < 4,i++ → i=0,交换 nums[0] 和 nums[1] → [2, 5, 3, 1, 4] j=2, nums[2]=3 < 4,i++ → i=1,交换 nums[1] 和 nums[2] → [2, 3, 5, 1, 4] j=3, nums[3]=1 < 4,i++ → i=2,交换 nums[2] 和 nums[3] → [2, 3, 1, 5, 4] 最后把 pivot 换到正确位置:交换 nums[i+1] 和 nums[right] → [2, 3, 1, 4, 5],pivot 4 的位置是 3 返回 3(pivot 最终位置) ``` > 💬 **Q:Lomuto 分区的时候,为什么大于基准的不动呢 不应该是小于基准的不动吗?** > > 关键在于 **i 指针追踪的是"小于 pivot 区域"的右边界**,所以"大的不动"是顺其自然,"小的要交换"是主动拉进小于区。 > > 扫描过程中,数组被分成四段: > > ``` > [left ... i] [i+1 ... j-1] [j ... right-1] [right] > < pivot >= pivot 还没看 pivot > ``` > > - `i` 指向"小于区"的最后一个位置 > - `i+1 ~ j-1` 这段是"大于等于区",**它是自动形成的,不需要专门维护** > > 当 `j` 扫到新元素时: > > - **`nums[j] >= pivot`(大的)**:它本来就该属于"大于等于区",而这个区域的右边界正是 `j-1`。下一次 `j++` 后,这个元素就自动被纳入进去了,**不用做任何操作**。 > - **`nums[j] < pivot`(小的)**:它要加入"小于区",但现在位置在"大于等于区"之后。所以 `i++` 把小于区扩大一格,再交换 `nums[i]` 和 `nums[j]`,把小的拉进来,把原来 `i` 位置上的大元素挤到 `j`(反正 `j` 下一步就走了,这个大元素就顺势留在"大于等于区"的末尾)。 > > 如果反过来想让"小的不动、大的动",就得改成:从右往左扫,`i` 追的是"大于区"的左边界。逻辑完全对称,只是方向反过来。Lomuto 的经典写法选的是前者。 > > **一句话总结**:i 指针在谁那边,谁就要"主动"被拉过来;另一边是"顺路"形成的。 ## 四步法 ``` 第 1 步:选基准 - 最简单:选区间最后一个元素 nums[right] - 更稳:随机选一个,避免最坏情况 O(n²) 第 2 步:分区 - 把数组重排成 [< pivot] pivot [> pivot] - 返回 pivot 的最终位置 pi 第 3 步:递归 - 对 [left, pi-1] 排序 - 对 [pi+1, right] 排序 第 4 步:递归出口 - left >= right 时,区间只有 0 或 1 个元素,已经有序 ``` ## 代码(Lomuto 分区) ```java public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); return nums; } private void quickSort(int[] nums, int left, int right) { if (left >= right) return; int pi = partition(nums, left, right); quickSort(nums, left, pi - 1); quickSort(nums, pi + 1, right); } private int partition(int[] nums, int left, int right) { // 随机选基准,防止最坏情况,可以注释掉这两行 int randomIdx = left + (int) (Math.random() * (right - left + 1)); swap(nums, randomIdx, right); int pivot = nums[right]; int i = left - 1; for (int j = left; j < right; j++) { if (nums[j] < pivot) { i++; swap(nums, i, j); } } swap(nums, i + 1, right); return i + 1; } private void swap(int[] nums, int a, int b) { int tmp = nums[a]; nums[a] = nums[b]; nums[b] = tmp; } ``` > 💬 **Q:循环外的两个 swap 为什么要这样做?** > > 这两个 swap 是 Lomuto 分区的点睛之笔,一个在循环前、一个在循环后,各有分工。 > > **第一个 swap:`swap(nums, randomIdx, right)`** > > 作用:把随机选中的元素**挪到末尾当 pivot**。 > > 为什么要挪?因为后面的循环 `for (int j = left; j < right; j++)` 扫描的是 `[left, right-1]`,不包含 `right`。这样写有两个好处: > > - 循环里不会扫到 pivot 自己,避免 pivot 跟自己比较的尴尬情况 > - pivot 被"安全地"藏在末尾不被打乱,扫描结束后再精准放回去 > > 如果不挪,让 pivot 留在随机位置,循环扫描时就得特判"跳过 pivot 所在的下标",写起来又丑又容易错。 > > **第二个 swap:`swap(nums, i + 1, right)`** > > 循环结束后,数组结构是这样的: > > ``` > [left ... i] [i+1 ... right-1] [right] > < pivot >= pivot pivot > ``` > > pivot 还在末尾待着,但它的**最终正确位置**应该在"小于区"和"大于等于区"之间,也就是下标 `i + 1`。 > > 所以把 `nums[i+1]`("大于等于区"的第一个元素)和 `nums[right]`(pivot)交换: > > - pivot 落到 `i + 1` > - 那个 ≥ pivot 的元素跑到末尾,正好接在"大于等于区"后面(因为它 ≥ pivot,跟在大于等于区末尾也合法) > > 交换后数组变成: > > ``` > [left ... i] pivot [i+2 ... right] > < pivot ↑ >= pivot > 最终位置 > ``` > > pivot 就被永久定格在 `i+1`,返回这个下标给上层,后续递归时跳过它。 > > **为什么是 `i+1` 不是 `i`?** > > `i` 指向"小于区"的最后一个位置,那里放着一个小于 pivot 的元素,不能被 pivot 覆盖掉。`i+1` 才是两个区域的分界点,也是 pivot 的归宿。 > 💬 **Q:随机选基准那两行可以注释掉吧?** > > **技术上可以,但强烈不建议**。注释掉程序依然能跑,逻辑完全正确,但在某些输入下会退化成 O(n²),甚至直接栈溢出。 > > **注释掉会出什么问题?** > > 去掉随机化后,pivot 永远是 `nums[right]`(区间最后一个元素)。遇到以下输入就会炸: > > ``` > 输入 1:已经有序的数组 [1, 2, 3, 4, 5, ..., n] > 第 1 轮:pivot = n,分区后 [1..n-1] | n | [] > 第 2 轮:pivot = n-1,分区后 [1..n-2] | n-1 | [] > 第 3 轮:pivot = n-2 ... > 每次分区都是"一边 n-1 个、另一边空",递归 n 层 > → 时间 O(n²),递归深度 n,大数组直接栈溢出 > > 输入 2:逆序数组 [n, n-1, ..., 2, 1] > 同样退化 > > 输入 3:全相同元素 [5, 5, 5, 5, 5] > 同样退化(Lomuto 分区对大量重复特别不友好) > ``` > > LeetCode 912 的测试用例里**就有**近乎有序和大量重复的数据,不加随机化几乎必挂。 > > **为什么随机化能救命?** > > 随机选 pivot 后,出现"极端分区"需要每一轮都撞上数组的最大/最小值。n 轮连续撞大运的概率是 `(2/n)^n`,小到可以忽略。期望情况下每次分区都能把数组大致平分,递归深度稳定在 O(log n)。 > > **替代方案** > > 如果觉得 `Math.random()` 有性能开销,可以换成: > > - **三数取中**:取 `nums[left]`、`nums[mid]`、`nums[right]` 三个数的中位数当 pivot,对有序数组也能稳定平分 > - **ThreadLocalRandom**:比 `Math.random()` 快一些 > > 但绝对不能"啥都不做"直接用末尾元素。这是工程实现里的一个著名血泪教训。 > > **结论**:这两行是防御性代码,不是可选功能。注释掉就像开车不系安全带,平时没事、出事要命。建议把源码注释里那句"可以注释掉这两行"理解成"这两行是用来防止退化的",而不是"可以省掉"。 ## 手动模拟(完整过程) ``` nums = [3, 6, 1, 5, 2, 4] 第 1 层:quickSort(0, 5) partition:pivot = 4(假设选最后一个) 扫一遍后:[3, 1, 2, 4, 5, 6],pi = 3 → 递归 quickSort(0, 2) 和 quickSort(4, 5) 第 2 层:quickSort(0, 2),子数组 [3, 1, 2] partition:pivot = 2 扫一遍后:[1, 2, 3],pi = 1 → 递归 quickSort(0, 0) 和 quickSort(2, 2)(都是单元素,直接返回) 第 2 层:quickSort(4, 5),子数组 [5, 6] partition:pivot = 6 扫一遍后:[5, 6],pi = 5 → 递归 quickSort(4, 4) 和 quickSort(6, 5)(都无需处理) 最终:[1, 2, 3, 4, 5, 6] ✓ ``` ## 复杂度分析 ``` 时间复杂度: 平均 O(n log n):每层分区 O(n),期望递归 log n 层 最坏 O(n²):每次都选到最大/最小当 pivot,退化成 n 层 - 比如数组已经有序,又选最后一个当 pivot - 解决:随机化选基准 空间复杂度: 平均 O(log n):递归栈深度 最坏 O(n):退化时递归栈深度变成 n ``` ## 为什么要随机选基准? ``` 不随机的话,对"近乎有序"的数组是灾难: nums = [1, 2, 3, 4, 5],每次选最后一个: 第 1 层:pivot = 5,分区后 [1,2,3,4] 和 [] 第 2 层:pivot = 4,分区后 [1,2,3] 和 [] 第 3 层:pivot = 3,分区后 [1,2] 和 [] ... 递归 n 层,每层 O(n),总复杂度 O(n²)。 随机选基准后,期望每次都能把数组大致平分,递归 log n 层,复杂度稳定在 O(n log n)。 ``` ## Hoare 分区(双指针,更快但更难写) ```java private int partition(int[] nums, int left, int right) { int pivot = nums[left]; int i = left - 1, j = right + 1; while (true) { do { i++; } while (nums[i] < pivot); do { j--; } while (nums[j] > pivot); if (i >= j) return j; swap(nums, i, j); } } // 递归调用要改成: // quickSort(nums, left, pi); // quickSort(nums, pi + 1, right); ``` Hoare 分区平均交换次数更少,但边界条件容易写错,不推荐新手用。 ## 三路快排(处理大量重复元素) 当数组里有很多重复元素时,Lomuto 和 Hoare 都会退化。三路快排把数组分成三段: ``` [ < pivot ] [ == pivot ] [ > pivot ] ``` 等于 pivot 的部分不再参与递归,大幅减少重复比较。 ```java private void quickSort3Way(int[] nums, int left, int right) { if (left >= right) return; int pivot = nums[left]; int lt = left, gt = right, i = left + 1; while (i <= gt) { if (nums[i] < pivot) swap(nums, i++, lt++); else if (nums[i] > pivot) swap(nums, i, gt--); else i++; } quickSort3Way(nums, left, lt - 1); quickSort3Way(nums, gt + 1, right); } ``` ## 注意:容易踩的坑 ``` Q:快排是稳定排序吗? A:不是。分区过程中会交换不相邻的元素,相等元素的相对顺序可能被打乱。 想要稳定排序用归并排序。 Q:为什么 LeetCode 912 不能用最朴素的快排? A:测试用例里有极端情况(比如大量重复元素或近乎有序的数组), 不加随机化会 TLE 或栈溢出。必须加随机化或用三路快排。 Q:partition 的返回值代表什么? A:pivot 最终所在的下标。这个位置左边全是 ≤ pivot 的, 右边全是 ≥ pivot 的,所以 pivot 这个位置不用再排了。 Q:快排和归并排序哪个快? A:理论上都是 O(n log n),但快排常数小、原地排序(空间 O(log n)), 实际工程中通常比归并排序快。JDK 的 Arrays.sort 对基本类型用的就是快排的变种。 ``` ## 应用:快速选择(Top-K 问题) 快排的分区思想还能用来 O(n) 找第 K 大元素(LeetCode 215): ```java // 利用 partition 的性质:返回 pi 后,pi 左边的数都比 pivot 小 // 所以只需要递归一边,不用全排 private int quickSelect(int[] nums, int left, int right, int k) { if (left == right) return nums[left]; int pi = partition(nums, left, right); if (pi == k) return nums[pi]; else if (pi < k) return quickSelect(nums, pi + 1, right, k); else return quickSelect(nums, left, pi - 1, k); } ``` 平均时间 O(n),比排完再取快得多。 > 💬 **Q:什么是快速选择算法?** > > 快速选择(Quick Select)是基于快排 partition 的变体,专门用于在无序数组中**找第 K 小/大的元素**,无需完整排序。 > > **核心思想**:每次 partition 后,pivot 落在最终位置 `p`,与目标 `k` 比较后只递归一侧: > > - `p == k` → 直接返回,找到了 > - `p > k` → 目标在左侧,递归 `[left, p-1]` > - `p < k` → 目标在右侧,递归 `[p+1, right]` > > **与快排的区别:** > > | | 快排 | 快速选择 | > |---|---|---| > | 目标 | 整个数组有序 | 找第 K 小/大的元素 | > | 递归方向 | 两侧都递归 | 只递归一侧 | > | 时间复杂度 | O(n log n) | 平均 O(n),最坏 O(n²) | > > **典型场景:LeetCode 215 数组中的第K个最大元素** > > 找第 K 大 = 找第 `n - K` 小(从 0 开始的下标),转化后套 quickSelect 即可: > > ```java > public int findKthLargest(int[] nums, int k) { > return quickSelect(nums, 0, nums.length - 1, nums.length - k); > } > > int quickSelect(int[] nums, int left, int right, int k) { > if (left == right) return nums[left]; > // 随机化防止最坏情况 > int randomIdx = left + (int)(Math.random() * (right - left + 1)); > swap(nums, randomIdx, right); > int p = partition(nums, left, right); > if (p == k) return nums[p]; > else if (p < k) return quickSelect(nums, p + 1, right, k); > else return quickSelect(nums, left, p - 1, k); > } > ``` > > 平均 O(n),远快于先排序再取 O(n log n),也比建堆 O(n log k) 在 k 较大时更优。 ## 一句话总结 快排 = 选基准 + 分区 + 递归左右。核心是 partition,关键是随机化选基准防止退化。平均 O(n log n),不稳定,原地排序。 --- 下一篇:[02 - 堆排序](./02-heap-sort.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入