【算法】分治 - 快速排序

快乐的流畅：个人主页

个人专栏：《算法神殿》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

---

引言

本节主要介绍快速排序（三路划分，随机取key），以及它的变形算法——快速选择算法

一、颜色分类

细节：快速排序中标准的partition（三路划分）

• 设置三个指针 left，cur，right
• 划分为三个区域[0, left - 1]，[left, right]，[right + 1, n-1]
• [0, left - 1]：元素小于key
• [left, right]：元素等于key
• [right + 1, n-1]：元素大于key
• left和right用来维护（等于key的）中路元素区域的左右两端，cur用来扫描数组

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;}}
};

二、排序数组

思路：

• 递归出口：区间只有一个元素或者不存在
• 随机选key：利用rand函数，记得提前srand种下随机数种子
• 三路划分：三指针维护区间
• 分治：继续递归[begin, left - 1]，[right + 1, end]两个区间

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);//随机选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);//种下随机数种子quickSort(nums, 0, nums.size() - 1);return nums;}
};

三、数组中的第k个数

思路：TopK问题有三种解法

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

堆版本

细节：建大堆 + 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)//执行k-1次{swap(nums[0], nums[nums.size() - 1]);nums.pop_back();AdjustDown(nums, 0);}return nums[0];}
};

快速选择版本

细节：

• 从最右边开始数，k落在右区域，则继续递归找第k大
• k落在中区域，则直接更新结果
• k落在左区域，则继续递归找第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个数

细节：

• 从最左边开始数，k落在左区域，则继续递归找最小的k个元素
• k落在中区域，则直接返回前k个元素
• k落在右区域，则继续递归找最小的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};}
};

总结

快速排序，随机选key，保证了时间复杂度逼近O(NlogN)，三路划分，是为了处理重复大量元素。

快速选择，是基于快速排序的变形算法，在解决TopK问题有着O(N)的时间复杂度，极其高效！

真诚点赞，手有余香