> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。
> 目标：熟练掌握分治快排算法。
> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。
> 专栏选自：刷题训练营
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：
⭐知识讲解
基本思想：
这个算法在我们学习数据结构中八大排序之快排，但这个快排比起数据结构中的快排简单不少，这个算在C语言中我们也涉及到了，如果大家对这个算法比较陌生的话，可以参考下面两篇博客，一个是数据结构中的另一个是C语言中的：
数据结构：手撕各种排序
C语言：快快快快快快快快快快排
特点：
我们下面题目所采用的方法都是三路划分法思想，这也和我们的标题分治不谋而合。
大致做题流程：
做题前一定要先画图，在写代码，如果能自己画出图来写代码轻松不少。
🌙topic-->1
题目链接：1.分治快-
题目分析：
题目意思比较简单，把数组中的0 1 2排序。
算法原理：
- 解法：采用三指针
图解：
细节处理：
left需要指向为 - 1，循环条件为 i < right.
代码演示：
class Solution { public: void sortColors(vector<int>& nums) { int n = nums.size(); // 定义三个指针 int left = -1,right = n,i = 0; // 循环 while(i < right) // 细节 { if(nums[i] == 0) swap(nums[++left],nums[i++]); else if(nums[i] == 1) i++; else swap(nums[--right],nums[i]); } } };
🌙topic-->2
题目链接：2.排序数组
题目分析：
给你一个整数数组 nums，请你将该数组升序排列。（解法有很多，我们采用快速排序算法）
算法原理：
- 解法：采用快速排序算法(三指针)
图解：
细节处理：
- 递归结束标志是 l >= r
代码演示：
class Solution { public: vector<int> sortArray(vector<int>& nums) { srand(time(NULL)); // 种下随机种子 qsort(nums, 0, nums.size() - 1); // 调用快速排序 return nums; // 返回数组 } // 快排 void qsort(vector<int>& nums,int l,int r) { if(l >= r) return; // 递归结束条件 // 数组分三块 int key = getRandom(nums, l, r); // 找一个对比值 int i = l,left = l - 1,right = r + 1; // 三个指针 // 循环 while(i < right) { if(nums[i] < key) swap(nums[++left],nums[i++]); else if(nums[i] == key) i++; else swap(nums[--right],nums[i]); } // 划分三个区域 [l ,left] [left + 1, right - 1] [right, r] qsort(nums ,l ,left); qsort(nums ,right ,r); } // 找对比值 int getRandom(vector<int>& nums ,int left,int right) { int r = rand(); return nums[r % (right - left + 1) + left]; } };
🌙topic-->3
题目链接：3. 数组中的第K个最大元素
题目分析：
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。（你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。）
算法原理：
- 解法：采用快速排序算法(三指针)
图解：
细节处理：
- 递归结束标志是 l == r
代码演示：
class Solution { public: int findKthLargest(vector<int>& nums, int k) { srand(time(NULL));// 种下随机种子 return qsort(nums, 0 ,nums.size() - 1, k); // 调用快排 } int qsort(vector<int>& nums, int l, int r, int k) { if(l == r) return nums[l];// 递归结束条件 // 随机选择基准元素 int key = getRandom(nums, l, r); // 数组分三块 int left = l - 1,right = r + 1,i = l; // 循环 while(i < right) { if(nums[i] < key) swap(nums[++left], nums[i++]); else if(nums[i] == key) i++; else swap(nums[--right], nums[i]); } // 讨论 int c = r - right + 1,b = right - left - 1; if(c >= k) return qsort(nums, right, r, k); else if(b + c >= k) return key; else return qsort(nums, l, left, k - b - c); } int getRandom(vector<int>& nums, int left, int right) { return nums[rand() % (right - left + 1) + left]; } };
🌙topic-->4
题目链接：
题目分析：
输入整数数组 arr，找出其中最小的 k 个数。（跟上面的题目相似，这里不在细致讲解）
算法原理：
- 解法：采用快速排序算法(三指针)
图解：
细节处理：
- 递归结束标志是 l >= r
代码演示：
class Solution { public: vector<int> getLeastNumbers(vector<int>&nums, int k) { srand(time(NULL)); qsort(nums, 0, nums.size() - 1, k); return { nums.begin(), nums.begin() + k }; } void qsort(vector<int>& nums, int l, int r, int k) { if (l >= r) return; // 1. 随机选择⼀个基准元素 + 数组分三块 int key = getRandom(nums, l, r); int left = l - 1, right = r + 1, i = l; while (i < right) { if (nums[i] < key) swap(nums[++left], nums[i++]); else if (nums[i] == key) i++; else swap(nums[--right], nums[i]); } // [l, left][left + 1, right - 1] [right, r] // 2. 分情况讨论 int a = left - l + 1, b = right - left - 1; if (a > k) qsort(nums, l, left, k); else if (a + b >= k) return; else qsort(nums, right, r, k - a - b); } int getRandom(vector<int>& nums, int l, int r) { return nums[rand() % (r - l + 1) + l]; } };
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
