【算法】分治 - 快速排序
引言
本节主要介绍快速排序（三路划分，随机取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);//随机选key
int 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问题有三种解法
- 排序——O(NlogN)
- 堆——O(NlogK)
- 快速选择——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)的时间复杂度，极其高效！
