快速排序和线性快速查找
事情要从一道力扣题目说起。
你看着题目名字，简直不是量身为堆排序设计的么，我反手一个大顶堆。。。等等
什么？强制要求时间复杂度O(n)。
好吧， 我是若智。看看题解先。
快速查找？
快速查找我会啊，不过时间复杂度也不是O(n)？管他，先查了再说！
思路是这样，类似使用快速排序把数组按照从大到小的顺序排序。使用基准元素，找到一个分割点pivot，分割点左边的元素都是大于基准数的，右边小于基准数。
然后！！！重点来了，正经的快速排序是继续分治下去，排序左区间和右区间。对于这个题目，只用检查pivot在该区间的排名是不是等于k就行了。
代码长这样：
class Solution {
public:
int partition(vector<int>& nums, int left, int right) {
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] <= nums[left]) {
j--;
}
while (i < j && nums[i] >= nums[left]) {
i++;
}
swap(nums[i], nums[j]);
}
swap(nums[left], nums[i]);
return i;
}
int quickSelect(vector<int>& nums, int left, int right, int k) {
int pivotIndex = partition(nums, left, right);
int rank = pivotIndex - left + 1; // 计算主元在当前子数组中的排名
if (rank == k) {
return nums[pivotIndex]; // 主元就是第 k 个最大的元素
} else if (rank < k) {
// 第 k 个最大的元素在主元右侧的子数组中
return quickSelect(nums, pivotIndex + 1, right, k - rank);
} else {
// 第 k 个最大的元素在主元左侧的子数组中
return quickSelect(nums, left, pivotIndex - 1, k);
}
}
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
return quickSelect(nums, 0, n - 1, k);
}
};
一切都是那么的美好。
嗯？你是故意找茬是不是！
好，不着急，冷静冷静，先分析分析时间效率。
最坏情况会进行n-1次分割，每次对子数组的一半进行交换。
语句次数：
$$ \frac{n-1}2+\frac{n-2}2+\ldots+1 $$ 那么时间复杂度为O(n^2)
所以是不满足题目要求的。
问题就在于分割时太不均衡了。
如果每次都分割n/2的话。
交换次数就是：
$$ n + \frac{n}{2} + \frac{n}{4} +…+ \frac{n}{n} = 2n -1 $$
就满足题目的要求 时间复杂度O(n)了。
那么怎么优化，能使分割尽量均匀呢。
我先想到的是随机基准数，不再像以前一样每次都使用第一个元素当做基准数，而是随机从数组中选择。
试了一试，最后一个测试用例还是超时。
看看题解大家都怎么说。
看k神的题解里提到了三路快速排序。什么玩意，知识盲区啊这是。
赶紧找文章恶补一下。
哦，学到了。
原来我之前一直用的，或者说默写的是二路快速排序啊我去。
一路：小于等于基准数的在同一个子数组。具体在 <v 还是 >v 看循环中的定义方式。
二路：=v 的元素分散在两个子数组
三路：=v的元素单独设置一个子数组
那为什么我的二路排序过不了捏。
重点是重复元素，在最后的测试用例里有大量的重复元素1，即使使用随机基准数、三数取中法都很容易选择数字1成为基准数，因此一路排序和二路排序都会存在大量的1的交换，使得时间效率很低。
使用三路排序，当1第一次成为基准数，就直接把所有的1划分的一个区间，后面就不需要再处理这些1了。
好的，现在来使用三路选择的方法解决原来的题目。
题目要求返回第k大元素，因此单调减的排序比较好操作。很简单调整gt(greater than)和lt(less than)的指针位置就好了，依葫芦画瓢，像下面这样。
检查k是否在 = v 的区间中，在的话直接返回该位置的数字；否则递归选择在左区间或者右区间查找。
三数取中法进一步提升代码健壮性，以达到接近O(n)的时间效率。
最终的代码如下
class Solution {
public:
// 三数取中法选择基准数，并调整基准数到 left 位置
void medianOfThree(vector<int>& nums, int left, int right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) swap(nums[mid], nums[right]);
if (nums[left] > nums[right]) swap(nums[left], nums[right]);
if (nums[mid] > nums[left]) swap(nums[mid], nums[left]);
// 此时，nums[left] 是中间值，将作为基准数
}
pair<int, int> partition(vector<int>& nums, int left, int right) {
medianOfThree(nums, left, right); // 优化基准数选择
int pivot = nums[left];
int gt = left, lt = right + 1;
int i = left + 1;
while (i < lt) {
if (nums[i] > pivot) {
swap(nums[i], nums[++gt]);
i++;
} else if (nums[i] < pivot) {
swap(nums[i], nums[--lt]);
} else {
i++;
}
}
swap(nums[left], nums[gt]);
return {gt - 1, lt};
}
int quickSelect(vector<int>& nums, int left, int right, int k) {
pair<int, int> p = partition(nums, left, right);
if (k - 1 > p.first && k - 1 < p.second) { // 修改此处
return nums[k - 1];
} else if (k - 1 <= p.first) { // 修改此处
return quickSelect(nums, left, p.first, k); // 修改此处
} else {
return quickSelect(nums, p.second, right, k); // 修改此处
}
}
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
return quickSelect(nums, 0, n - 1, k);
}
};