目录
颜色分类
题解：
排序数组
题解：
TOP K 问题 -- 快速选择算法
数组中的第 K 个最大的元素
题解：
数组中最小的 K 个数
题解：
对于数组，一开始就要定好区间是左闭右闭、左闭右开、左开右闭还是左开右开！
颜色分类
75. 颜色分类 - 力扣（LeetCode）
https://leetcode.cn/problems/sort-colors/
题解：
用到的方法和二分查找的移动零类似。
- 用 left 、right 和 i 指针把数组分为四部分：[ 0 , left ] 存放的是数字 0，[ left+1 , i-1 ] 存放的是数字1，[ i , right - 1 ] 是还没有遍历的数字，[ right , n-1 ] 存放的是数字 2.
当 i 和 right 相遇时，整个数组也归类完毕，[ 0 , left ] 存的是数字 0，[ left+1 , right-1 ] 存的是数字 1，[ right , n-1 ] 存的是数字 2！
- 要注意 left 和 right 的初始值，left = -1，right = n，因为初始时整个数组都还没有遍历，一切的数字都还没有归类，不能直接认为下标为 0 的位置存放的就是 0，下标 n-1 的位置存放的就是 2 ！
- 要注意是 i<right，而不是 i < n，这样分类会出错！
- 要注意和 left 位置交换时 i++，和 right 位置交换时 i 不用++ 。
class Solution {
public:void sortColors(vector<int>& nums) {int n=nums.size();int left=-1,right=n;for(int i=0;i<right;){if(nums[i]==0) swap(nums[++left],nums[i++]);else if(nums[i]==1) ++i;else swap(nums[--right],nums[i]);}}
};排序数组
912. 排序数组 - 力扣（LeetCode）https://leetcode.cn/problems/sort-an-array/description/
题解：
快速排序：数组分三块+选key值
快速排序的思路和颜色分类类似，排序的过程类似于一个分类的过程，为了分类，我们需要选出一个 key 值作为标准。随机选择数组中的一个数作为 key 值即可。
把小于 key 值的数字放到 key 的左边，等于 key 值的数字放在中间，大于 key 值得数字放到 key 的右边。如下图：
第一次分类后，[ 0 , left ] 都是比 key 小的数， [ right , n-1 ] 都是比 key 大的数，但是这两个区间里面的数还是乱序的，所以需要在这两个区间内分别选择 key 值，继续归类排序。
由于排序的思路都是类似的，只是区间有所差异，函数可以选择需要排序的区间的左端点和右端点作为参数，我们选择区间为左闭右闭。
for 循环内的代码是快速排序算法的核心，需要理解掌握！
class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(NULL));int n=nums.size();myqsort(nums,0,n-1);//左闭右闭return nums;}void myqsort(vector<int>& nums,int begin,int end){if(begin>=end) return;int key=FindKey(nums,begin,end);int left=begin-1,right=end+1;//左开右开//[begin,left][left+1,i][i,right-1][right,end]//->[begin,left][left+1,right-1][right,end]for(int i=begin;i<right;){if(nums[i]<key) swap(nums[++left],nums[i++]);else if(nums[i]==key) i++;else swap(nums[--right],nums[i]);}myqsort(nums,begin,left); myqsort(nums,right,end);}int FindKey(vector<int>& nums,int left,int right){//随机选择 key 值int t=rand();return nums[t%(right-left+1)+left];}
};TOP K 问题 -- 快速选择算法
数组中的第 K 个最大的元素
215. 数组中的第K个最大元素 - 力扣（LeetCode）https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
题解：
由于是找出第 K 个最大的元素，其实并不需要把所有的元素都排序后返回第 K 大的元素。
在第一次分类后，[ 0 , left ] 都是比 key 值小的数（假设区间长度为 a）， [ left+1 , right-1 ] 都是等于 key 值的数（假设区间长度为 b）， [ right , end ] 都是比 key 值大的数（假设区间长度为 c）。
如果第 K 大的元素落在 [ right , end ] 区间，即第 K 大的元素比 key 值大，即 c >= K，那么 [ 0 , left ] 区间就没有必要排序了，只需要排序 [ right , end ] 区间，在 [ right , end ] 区间 内找到第 K 大的元素即可；
如果第 K 大的元素落在 [ left+1，right-1 ] 区间，恰好等于 key 值，即 b+c >= K，那么直接返回 key 值即可，没有必要继续排序了；
如果第 K 大的元素落在 [ 0 , left ] 区间，即 K > b+c，那么 [ right , end ] 区间就没有必要排序了，只需要排序 [ 0 , left ] 区间，此时只需要在 [ 0 , left ] 中找到第 K - b - c 大的数即可；
所以这道题只是在排序数组的基础上，增加下一步需要对哪个区间排序的判断而已。
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {srand(time(NULL));return _FindKthLargest(nums,0,nums.size()-1,k);//左闭右闭}int _FindKthLargest(vector<int>& nums, int begin,int end,int k){if(begin==end) return nums[begin];int key=getKey(nums,begin,end);//左闭右闭int left=begin-1,right=end+1;for(int i=begin;i<right;){if(nums[i]<key) swap(nums[++left],nums[i++]);else if(nums[i]==key) i++;else swap(nums[--right],nums[i]);}if(end-right+1>=k) return _FindKthLargest(nums,right,end,k);else if(end-left>=k) return key;else return _FindKthLargest(nums,begin,left,k-end+left);}int getKey(vector<int>& nums,int left,int right){return nums[rand()%(right-left+1)+left];//左闭右闭}
};数组中最小的 K 个数
LCR 159. 库存管理 III - 力扣（LeetCode）https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/description/
题解：
这一道题其实就是找去数组中最小的 K个数，和上一题的思路类似：
如果最小的 K 个数在 [ 0 , left ] 中，即 a > K，那么只需要对 [ 0 , left ] 区间进行排序；
如果最小的 K 个数落在 [ 0 , right-1 ] 区间内，即 a+b >= K，那么直接返回即可，不需要继续排序了；
如果不符合上面两种的情况，那么需要对 [ right , end ] 区间进行排序，找出区间内最小的 K-a-b 个数即可。
class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(NULL));_inventoryManagement(stock,0,stock.size()-1,cnt);//左闭右闭return {stock.begin(),stock.begin()+cnt};}void _inventoryManagement(vector<int>& stock, int begin,int end,int k){if(begin==end) return;int key=getKey(stock,begin,end);//左闭右闭int left=begin-1,right=end+1;for(int i=begin;i<right;){if(stock[i]<key) swap(stock[++left],stock[i++]);else if(stock[i]==key) i++;else swap(stock[--right],stock[i]);}//[begin,left][left+1,,right-1][right,end]int a=left-begin+1,b=right-left-1,c=end-right+1;if(a>k) _inventoryManagement(stock,begin,left,k);else if(a+b>=k) return;else _inventoryManagement(stock,right,end,k-a-b);}int getKey(vector<int>& stock, int begin,int end){return stock[rand()%(end-begin+1)+begin];}
};