当前位置：首页 > news >正文

【优选算法篇】快速排序模型——从数组划分到快速选择

news 2026/8/26 23:53:50

文章目录

分治的真谛：三指针划分与随机化基准

一、前言：快排的“死穴”与进化

💬开篇：传统的快速排序（双指针划分）在遇到大量重复元素或者有序数组时，时间复杂度会退化到O ( N 2 ) O(N^2)O(N2)。
🚀进化方向：
三指针划分（荷兰国旗思想）：将数组一次性分为“小于”、“等于”、“大于”三块。遇到大量重复元素时，中间的“等于块”直接跳过，效率提升数倍！
随机基准（Random Pivot）：通过数学概率，将最坏情况发生的概率降到几乎为零。
👍点赞收藏：这篇的代码模板是目前面试和竞赛中最通用的“万能快排模板”，建议背诵并默写！🔥

二、颜色分类：数组分三块 (Medium)

2.1 题目描述

题目链接：75. 颜色分类
描述：
数组nums包含红色(0)、白色(1)和蓝色(2)。原地排序，使相同颜色相邻，顺序为红、白、蓝。
要求：不使用sort函数，一次遍历完成。

2.2 深度拆解：三指针算法 (Dutch National Flag)

我们要把数组划分为：[0...0, 1...1, 待处理, 2...2]。
定义三个指针：

left：指向0 序列的末尾（初始为 -1）。
right：指向2 序列的开头（初始为 n）。
cur：正在扫描的位置（初始为 0）。

扫描逻辑（数学归纳与证明）：

nums[cur] == 0：把它甩到左边。执行swap(nums[++left], nums[cur++])。
- 证明：left+1位置一定是 1（或者就是cur本身），交换后cur拿到的新数是确定过的，所以cur放心右移。
nums[cur] == 1：位置正确，不管它。执行cur++。
nums[cur] == 2：把它甩到右边。执行swap(nums[--right], nums[cur])。
- 证明：交换过来的数是从右边还没看过的区域拿的，不知道是什么，所以cur不能移动，下一轮必须原地再检查一遍！

ASCII 状态图：

[00|111|? ? ?|22]^ ^ ^ left cur right

2.3 C++ 代码实战

classSolution{public:voidsortColors(vector<int>&nums){intn=nums.size();intleft=-1,right=n,cur=0;while(cur<right){if(nums[cur]==0){// 把 0 换到左边去swap(nums[++left],nums[cur++]);}elseif(nums[cur]==1){// 1 本来就在中间，继续扫描cur++;}else{// 把 2 换到右边去// 重点：换过来的数没看过，cur 不能加！swap(nums[--right],nums[cur]);}}}};

三、快速排序：三块划分 + 随机基准 (Medium)

3.1 题目描述

题目链接：912. 排序数组
描述：升序排列数组。

3.2 策略进化：为什么要随机化？

如果每次都选第一个数当基准（Pivot），给一个已经排好序的数组排序，快排就变成了“冒泡”，时间复杂度O ( N 2 ) O(N^2)O(N2)。
随机化证明：通过随机选择一个位置作为基准，任何一种特定的输入都无法稳定地触发快排的最坏情况。数学上，其期望时间复杂度为严格的O ( N log ⁡ N ) O(N \log N)O(NlogN)。

结合数组分三块，我们在递归时：

左边递归：[l, left]
右边递归：[right, r]
中间的等于块[left + 1, right - 1]已经归位，直接无视！这种剪枝在处理全重复数组时速度是惊人的O ( N ) O(N)O(N)。

3.3 C++ 代码实战（万能快排模板）

classSolution{public:vector<int>sortArray(vector<int>&nums){srand(time(NULL));// 种下随机数种子quickSort(nums,0,nums.size()-1);returnnums;}voidquickSort(vector<int>&nums,intl,intr){if(l>=r)return;// 1. 随机选择基准元素intkey=nums[rand()%(r-l+1)+l];// 2. 三指针划分 (荷兰国旗)intleft=l-1,right=r+1,cur=l;while(cur<right){if(nums[cur]<key)swap(nums[++left],nums[cur++]);elseif(nums[cur]==key)cur++;elseswap(nums[--right],nums[cur]);}// 3. 递归左右区间 [l, left] 和 [right, r]// 注意：中间的等于 key 的部分 [left + 1, right - 1] 已经不动了quickSort(nums,l,left);quickSort(nums,right,r);}};

四、快速选择算法：数组中的第 K 个最大元素 (Medium)

4.1 题目描述

题目链接：215. 数组中的第 K 个最大元素
描述：找出排序后的第k个最大的元素。要求O ( N ) O(N)O(N)时间复杂度。

4.2 深度拆解：为什么是 O(N)？

如果全排好序再拿，是O ( N log ⁡ N ) O(N \log N)O(NlogN)。
但在快排划分三块后：

大于区（右块）个数为c。
等于区（中块）个数为b。
小于区（左块）个数为a。

贪心决策：

如果c >= k：说明第k大一定在右块，直接去右块找。
如果c + b >= k：说明第k大正好落在等于区，直接返回key！
否则：说明第k大在左块，要去左块找。

数学证明：
每次只进入一侧，总遍历量为N + N / 2 + N / 4 ⋯ = 2 N N + N/2 + N/4 \dots = 2NN+N/2+N/4⋯=2N。
因此时间复杂度为严格的O ( N ) O(N)O(N)。

4.3 C++ 代码实战

classSolution{public:intfindKthLargest(vector<int>&nums,intk){srand(time(NULL));returnquickSelect(nums,0,nums.size()-1,k);}intquickSelect(vector<int>&nums,intl,intr,intk){if(l==r)returnnums[l];// 1. 随机选基准并分三块intkey=nums[rand()%(r-l+1)+l];intleft=l-1,right=r+1,cur=l;while(cur<right){if(nums[cur]<key)swap(nums[++left],nums[cur++]);elseif(nums[cur]==key)cur++;elseswap(nums[--right],nums[cur]);}// 2. 统计各块元素个数intc=r-right+1;// 大于区个数intb=right-left-1;// 等于区个数// 3. 分情况讨论if(c>=k){returnquickSelect(nums,right,r,k);}elseif(b+c>=k){returnkey;}else{// 去左块找，k 要更新（扣掉右块和中块的个数）returnquickSelect(nums,l,left,k-b-c);}}};

五、最小的 K 个数 (Medium)

5.1 题目描述

题目链接：LCR 159. 库存管理（原：最小的 k 个数）
描述：找出数组中最小的k个数。

5.2 核心思路

与“第 K 大”完全对称。
三块划分后：[左块(a个), 中块(b个), 右块(c个)]。

如果a > k：去左块继续找。
如果a + b >= k：中块和左块的部分已经凑够 k 个了，直接结束递归。
如果a + b < k：左块和中块全拿走，再去右块找剩下的k - a - b个。

5.3 C++ 代码实战

classSolution{public:vector<int>inventoryManagement(vector<int>&stock,intcnt){srand(time(NULL));qsort(stock,0,stock.size()-1,cnt);// 返回前 cnt 个元素即可return{stock.begin(),stock.begin()+cnt};}voidqsort(vector<int>&nums,intl,intr,intk){if(l>=r)return;intkey=nums[rand()%(r-l+1)+l];intleft=l-1,right=r+1,cur=l;while(cur<right){if(nums[cur]<key)swap(nums[++left],nums[cur++]);elseif(nums[cur]==key)cur++;elseswap(nums[--right],nums[cur]);}// a: 小于区个数, b: 等于区个数inta=left-l+1,b=right-left-1;if(a>k){qsort(nums,l,left,k);}elseif(a+b>=k){return;// 凑够了，收工}else{// 左块中块都要了，去右边找剩下的qsort(nums,right,r,k-a-b);}}};