快排算法 （分治实现）

本算法采用将整个数组划分成三个部分 <key  =key  >key 

在数组全是同一个数字时，也能达到NlogN的时间复杂度

下面的板书中i为遍历数组的下标

left为<key的最右边的下标

right为>key的最左边的下标

例题1：912. 排序数组 - 力扣（LeetCode）

例题2：LCR 159. 库存管理 III - 力扣（LeetCode）

答案1：

class Solution {
public://统一全传begin和endint Getrand(int begin ,int end){return (rand()%(end-begin+1)+begin);} void qsort(vector<int>& nums, int begin ,int end){if(begin>= end) return;int key =nums[Getrand(begin ,end)];//数组分三块int i=begin ,left =begin-1,right=end+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]);}//[begin left][left+1 right-1][right end]qsort(nums ,begin,left);qsort(nums ,right ,end);}vector<int> sortArray(vector<int>& nums) {srand(time(nullptr));qsort(nums ,0 ,nums.size()-1);return nums;}
};

答案2：

class Solution {
public:int Getrand(int begin ,int end){return (rand()%(end-begin+1)+begin);}void qsort(vector<int>& stock ,int begin ,int end){if(begin>= end) return;int key =stock[Getrand(begin ,end)];//数组分三块int i=begin ,left =begin-1 ,right =end+1;//left是小于key ,right是大于keywhile(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]qsort(stock ,begin,left);qsort(stock ,right ,end);}vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(nullptr));qsort(stock ,0 ,stock.size()-1);vector<int> ret;int i=0;while(cnt--){ret.push_back(stock[i++]);}return ret;}
};