快樂的流暢：個人主頁

個人專欄：《算法神殿》《數(shù)據(jù)結(jié)構(gòu)世界》《進(jìn)擊的C++》

遠(yuǎn)方有一堆篝火，在為久候之人燃燒！

---

引言

本節(jié)主要介紹快速排序（三路劃分，隨機(jī)取key），以及它的變形算法——快速選擇算法

一、顏色分類

細(xì)節(jié)：快速排序中標(biāo)準(zhǔn)的partition（三路劃分）

• 設(shè)置三個指針 left，cur，right
• 劃分為三個區(qū)域[0, left - 1]，[left, right]，[right + 1, n-1]
• [0, left - 1]：元素小于key
• [left, right]：元素等于key
• [right + 1, n-1]：元素大于key
• left和right用來維護(hù)（等于key的）中路元素區(qū)域的左右兩端，cur用來掃描數(shù)組

class Solution
{
public:void sortColors(vector<int>& nums){int left = 0, cur = 0, right = nums.size() - 1;while(cur <= right){if(nums[cur] == 0) swap(nums[left++], nums[cur++]);else if(nums[cur] == 2) swap(nums[right--], nums[cur]);else ++cur;}}
};

二、排序數(shù)組

思路：

• 遞歸出口：區(qū)間只有一個元素或者不存在
• 隨機(jī)選key：利用rand函數(shù)，記得提前srand種下隨機(jī)數(shù)種子
• 三路劃分：三指針維護(hù)區(qū)間
• 分治：繼續(xù)遞歸[begin, left - 1]，[right + 1, end]兩個區(qū)間

class Solution
{
public:int getKey(vector<int>& nums, int left, int right){int keyi = rand() % (right - left + 1) + left;return nums[keyi];}void quickSort(vector<int>& nums, int begin, int end){if(begin >= end) return;int key = getKey(nums, begin, end);//隨機(jī)選keyint cur = begin, left = begin, right = end;while(cur <= right){if(nums[cur] < key) swap(nums[left++], nums[cur++]);else if(nums[cur] > key) swap(nums[right--], nums[cur]);else cur++;}quickSort(nums, begin, left - 1);quickSort(nums, right + 1, end);}vector<int> sortArray(vector<int>& nums){srand(0);//種下隨機(jī)數(shù)種子quickSort(nums, 0, nums.size() - 1);return nums;}
};

三、數(shù)組中的第k個數(shù)

思路：TopK問題有三種解法

1. 排序——O(NlogN)
2. 堆——O(NlogK)
3. 快速選擇——O(N)

堆版本

細(xì)節(jié)：建大堆 + k-1次刪除

class Solution
{
public:void AdjustDown(vector<int>& nums, int parent){int n = nums.size(), child = 2 * parent + 1;while(child < n){if(child + 1 < n && nums[child] < nums[child + 1]) ++child;if(nums[parent] < nums[child])//建大堆{swap(nums[parent], nums[child]);parent = child;child = 2 * parent + 1;}else break;}}int findKthLargest(vector<int>& nums, int k){int n = nums.size();for(int i=(n-1-1)/2; i>=0; --i){AdjustDown(nums, i);}while(--k)//執(zhí)行k-1次{swap(nums[0], nums[nums.size() - 1]);nums.pop_back();AdjustDown(nums, 0);}return nums[0];}
};

快速選擇版本

細(xì)節(jié)：

• 從最右邊開始數(shù)，k落在右區(qū)域，則繼續(xù)遞歸找第k大
• k落在中區(qū)域，則直接更新結(jié)果
• k落在左區(qū)域，則繼續(xù)遞歸找第k-b-c大

class Solution
{int ret;
public:int GetKey(vector<int>& nums, int begin, int end){int keyi = rand() % (end - begin + 1) + begin;return nums[keyi];}void qucikSelect(vector<int>& nums, int begin, int end, int k){if(begin > end) return;int key = GetKey(nums, begin, end);int left = begin, cur = begin, right = end;while(cur <= right){if(nums[cur] < key) swap(nums[left++], nums[cur++]);else if(nums[cur] > key) swap(nums[right--], nums[cur]);else cur++;}if(k <= end - right) qucikSelect(nums, right + 1, end, k);else if(k <= end - left + 1) ret = key;else qucikSelect(nums, begin, left - 1, k - (end - left + 1));}int findKthLargest(vector<int>& nums, int k){srand(0);qucikSelect(nums, 0, nums.size() - 1, k);return ret;}
};

四、最小的k個數(shù)

細(xì)節(jié)：

• 從最左邊開始數(shù)，k落在左區(qū)域，則繼續(xù)遞歸找最小的k個元素
• k落在中區(qū)域，則直接返回前k個元素
• k落在右區(qū)域，則繼續(xù)遞歸找最小的k-a-b個元素

class Solution
{
public:int getKey(vector<int>& nums, int begin, int end){int keyi = rand() % (end - begin + 1) + begin;return nums[keyi];}void quickSelect(vector<int>& nums, int begin, int end, int k){if(begin >= end) return;int key = getKey(nums, begin, end);int left = begin, cur = begin, right = end;while(cur <= right){if(nums[cur] < key) swap(nums[left++], nums[cur++]);else if(nums[cur] > key) swap(nums[right--], nums[cur]);else cur++;}if(k <= left - begin) quickSelect(nums, begin, left - 1, k);else if(k <= right + 1 - begin) return;else quickSelect(nums, right + 1, end, k - (right + 1 - begin));}vector<int> inventoryManagement(vector<int>& nums, int k){srand(0);quickSelect(nums, 0, nums.size() - 1, k);return {nums.begin(), nums.begin() + k};}
};

總結(jié)

快速排序，隨機(jī)選key，保證了時間復(fù)雜度逼近O(NlogN)，三路劃分，是為了處理重復(fù)大量元素。

快速選擇，是基于快速排序的變形算法，在解決TopK問題有著O(N)的時間復(fù)雜度，極其高效！

真誠點贊，手有余香