Leetcode-在未排序的数组中找到第 k 个最大的元素（中等）

在未排序的数组中找到第 k 个最大的元素

//快排
//注意找到轴值的索引等于k即可停止，大于k时排左边，否则排右边
class Solution {
public:
    int QuickSort(vector<int>& nums, int left, int right, int k) {
        //if(left>=right)一定能找到，所以不需要考虑一边全遍历完的情况
        int central = partition(nums, left, right);
        if (central == k)
            return nums[central];
        if (central > k)
            return QuickSort(nums, left, central - 1, k);//什么时候找到什么时候return
        else
            return QuickSort(nums, central + 1, right, k);
    }
    int partition(vector<int>& nums, int left, int right) {
        srand(time(0));
        int pivot = rand() % (right - left + 1) + left;
        swap(nums[left], nums[pivot]);
        int lt = left;//less than 小于等于lt的一定是小于privot元素的
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < nums[left])
            {
                lt++;
                swap(nums[lt], nums[i]);
            }
        }
        swap(nums[left], nums[lt]);
        return lt;//中心位置
    }
    int findKthLargest(vector<int>& nums, int k) {

        return QuickSort(nums, 0, nums.size() - 1, nums.size() - k);
    }
};

快排排序：

    //需要两个函数
//void QuickSort(vector<int>& nums, int left, int right)用来递归，找到轴值，递归左右两边
//int partition(vector<int>& nums, int left, int right) 负责找到轴值，小于它的放左边，大于它的放右边，并返回中心轴值所在索引

class Solution {
public:
    void QuickSort(vector<int>& nums, int left, int right) {
        if (left >= right)//当左边没有元素的时候，会出现left<right的情况；只有一个元素时相等
            return;
        int central = partition(nums, left, right);//找到轴值，把低于它的放左边，高于他的放右边
        QuickSort(nums, left, central - 1);//继续对左边排序
        QuickSort(nums, central + 1, right);//继续对一边排序
    }
    int partition(vector<int>& nums, int left, int right) {
        srand(time(0));
        int pivot = rand() % (right - left + 1) + left;//找到随机轴值，交换至首位
        swap(nums[left], nums[pivot]);
        int lt = left;//less than      lt的本身和左边一定是小于privot元素的，从首位开始
        for (int i = left + 1; i <= right; i++) {//i从首位右边开始遍历，大于轴值的不动，小于轴值的交换
            if (nums[i] < nums[left])
            {
                lt++; //lt右移，腾出位置将小于的值交换过来，保持lt左边和本身都是小于轴值的
                swap(nums[lt], nums[i]);
            }
        }
        swap(nums[left], nums[lt]);//将首位的轴值交换到lt位置 此时：小于 轴值 大于
        return lt;//轴值所在的中心位置
    }
    void findKthLargest(vector<int>& nums) {
        QuickSort(nums, 0, nums.size() - 1);
    }
};