文章目录分治的真谛三指针划分与随机化基准一、 前言快排的“死穴”与进化二、 颜色分类数组分三块 (Medium)2.1 题目描述2.2 深度拆解三指针算法 (Dutch National Flag)2.3 C 代码实战三、 快速排序三块划分 随机基准 (Medium)3.1 题目描述3.2 策略进化为什么要随机化3.3 C 代码实战万能快排模板四、 快速选择算法数组中的第 K 个最大元素 (Medium)4.1 题目描述4.2 深度拆解为什么是 O(N)4.3 C 代码实战五、 最小的 K 个数 (Medium)5.1 题目描述5.2 核心思路5.3 C 代码实战六、 总结分治的真谛三指针划分与随机化基准一、 前言快排的“死穴”与进化开篇传统的快速排序双指针划分在遇到大量重复元素或者有序数组时时间复杂度会退化到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])。证明left1位置一定是 1或者就是cur本身交换后cur拿到的新数是确定过的所以cur放心右移。nums[cur] 1位置正确不管它。执行cur。nums[cur] 2把它甩到右边。执行swap(nums[--right], nums[cur])。证明交换过来的数是从右边还没看过的区域拿的不知道是什么所以cur不能移动下一轮必须原地再检查一遍ASCII 状态图[00|111|? ? ?|22]^ ^ ^ left cur right2.3 C 代码实战classSolution{public:voidsortColors(vectorintnums){intnnums.size();intleft-1,rightn,cur0;while(curright){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:vectorintsortArray(vectorintnums){srand(time(NULL));// 种下随机数种子quickSort(nums,0,nums.size()-1);returnnums;}voidquickSort(vectorintnums,intl,intr){if(lr)return;// 1. 随机选择基准元素intkeynums[rand()%(r-l1)l];// 2. 三指针划分 (荷兰国旗)intleftl-1,rightr1,curl;while(curright){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 2NNN/2N/4⋯2N。因此时间复杂度为严格的O ( N ) O(N)O(N)。4.3 C 代码实战classSolution{public:intfindKthLargest(vectorintnums,intk){srand(time(NULL));returnquickSelect(nums,0,nums.size()-1,k);}intquickSelect(vectorintnums,intl,intr,intk){if(lr)returnnums[l];// 1. 随机选基准并分三块intkeynums[rand()%(r-l1)l];intleftl-1,rightr1,curl;while(curright){if(nums[cur]key)swap(nums[left],nums[cur]);elseif(nums[cur]key)cur;elseswap(nums[--right],nums[cur]);}// 2. 统计各块元素个数intcr-right1;// 大于区个数intbright-left-1;// 等于区个数// 3. 分情况讨论if(ck){returnquickSelect(nums,right,r,k);}elseif(bck){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:vectorintinventoryManagement(vectorintstock,intcnt){srand(time(NULL));qsort(stock,0,stock.size()-1,cnt);// 返回前 cnt 个元素即可return{stock.begin(),stock.begin()cnt};}voidqsort(vectorintnums,intl,intr,intk){if(lr)return;intkeynums[rand()%(r-l1)l];intleftl-1,rightr1,curl;while(curright){if(nums[cur]key)swap(nums[left],nums[cur]);elseif(nums[cur]key)cur;elseswap(nums[--right],nums[cur]);}// a: 小于区个数, b: 等于区个数intaleft-l1,bright-left-1;if(ak){qsort(nums,l,left,k);}elseif(abk){return;// 凑够了收工}else{// 左块中块都要了去右边找剩下的qsort(nums,right,r,k-a-b);}}};六、 总结复盘快排并不难难的是如何处理那些“极端输入”。分三块Dutch National Flag是对抗重复元素的最强武器。随机化Randomization是对抗有序数组的唯一解。快速选择Quick Select是在不完全排序的前提下通过“剪枝”实现O ( N ) O(N)O(N)统计的数学神迹。
【优选算法篇】快速排序模型——从数组划分到快速选择
文章目录分治的真谛三指针划分与随机化基准一、 前言快排的“死穴”与进化二、 颜色分类数组分三块 (Medium)2.1 题目描述2.2 深度拆解三指针算法 (Dutch National Flag)2.3 C 代码实战三、 快速排序三块划分 随机基准 (Medium)3.1 题目描述3.2 策略进化为什么要随机化3.3 C 代码实战万能快排模板四、 快速选择算法数组中的第 K 个最大元素 (Medium)4.1 题目描述4.2 深度拆解为什么是 O(N)4.3 C 代码实战五、 最小的 K 个数 (Medium)5.1 题目描述5.2 核心思路5.3 C 代码实战六、 总结分治的真谛三指针划分与随机化基准一、 前言快排的“死穴”与进化开篇传统的快速排序双指针划分在遇到大量重复元素或者有序数组时时间复杂度会退化到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])。证明left1位置一定是 1或者就是cur本身交换后cur拿到的新数是确定过的所以cur放心右移。nums[cur] 1位置正确不管它。执行cur。nums[cur] 2把它甩到右边。执行swap(nums[--right], nums[cur])。证明交换过来的数是从右边还没看过的区域拿的不知道是什么所以cur不能移动下一轮必须原地再检查一遍ASCII 状态图[00|111|? ? ?|22]^ ^ ^ left cur right2.3 C 代码实战classSolution{public:voidsortColors(vectorintnums){intnnums.size();intleft-1,rightn,cur0;while(curright){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:vectorintsortArray(vectorintnums){srand(time(NULL));// 种下随机数种子quickSort(nums,0,nums.size()-1);returnnums;}voidquickSort(vectorintnums,intl,intr){if(lr)return;// 1. 随机选择基准元素intkeynums[rand()%(r-l1)l];// 2. 三指针划分 (荷兰国旗)intleftl-1,rightr1,curl;while(curright){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 2NNN/2N/4⋯2N。因此时间复杂度为严格的O ( N ) O(N)O(N)。4.3 C 代码实战classSolution{public:intfindKthLargest(vectorintnums,intk){srand(time(NULL));returnquickSelect(nums,0,nums.size()-1,k);}intquickSelect(vectorintnums,intl,intr,intk){if(lr)returnnums[l];// 1. 随机选基准并分三块intkeynums[rand()%(r-l1)l];intleftl-1,rightr1,curl;while(curright){if(nums[cur]key)swap(nums[left],nums[cur]);elseif(nums[cur]key)cur;elseswap(nums[--right],nums[cur]);}// 2. 统计各块元素个数intcr-right1;// 大于区个数intbright-left-1;// 等于区个数// 3. 分情况讨论if(ck){returnquickSelect(nums,right,r,k);}elseif(bck){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:vectorintinventoryManagement(vectorintstock,intcnt){srand(time(NULL));qsort(stock,0,stock.size()-1,cnt);// 返回前 cnt 个元素即可return{stock.begin(),stock.begin()cnt};}voidqsort(vectorintnums,intl,intr,intk){if(lr)return;intkeynums[rand()%(r-l1)l];intleftl-1,rightr1,curl;while(curright){if(nums[cur]key)swap(nums[left],nums[cur]);elseif(nums[cur]key)cur;elseswap(nums[--right],nums[cur]);}// a: 小于区个数, b: 等于区个数intaleft-l1,bright-left-1;if(ak){qsort(nums,l,left,k);}elseif(abk){return;// 凑够了收工}else{// 左块中块都要了去右边找剩下的qsort(nums,right,r,k-a-b);}}};六、 总结复盘快排并不难难的是如何处理那些“极端输入”。分三块Dutch National Flag是对抗重复元素的最强武器。随机化Randomization是对抗有序数组的唯一解。快速选择Quick Select是在不完全排序的前提下通过“剪枝”实现O ( N ) O(N)O(N)统计的数学神迹。
