快速排序和线性快速查找

事情要从一道力扣题目说起。

215. 数组中的第K个最大元素

你看着题目名字，简直不是量身为堆排序设计的么，我反手一个大顶堆。。。等等

什么？强制要求时间复杂度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次分割，每次对子数组的一半进行交换。

语句次数：

那么时间复杂度为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);
    }
};