思路：

• 欲求第k大的元素，可以对序列进行降序排序，排序后序列下标为k - 1的元素即是第k大元素；
• 排序的思路与快速排序相同，但不需要对整个序列进行排序，在快排模板末尾加上一个if条件判断即可。

class Solution {
public:
    int quick_select(vector<int>& nums, int left, int right, int k)
    {
        //若left等于right则表示序列已经完成排序，直接返回第k个元素即可
        if (left == right) return nums[k];

        int pivot = nums[left], i = left - 1, j = right + 1;
        while (i < j)
        {
            do i ++ ; while (nums[i] > pivot);      //若这两行的大于小于号对调便是升序排序
            do j -- ; while (nums[j] < pivot);
            if (i < j) swap(nums[i], nums[j]);
        }

        //注意退出循环后i与j不一定是相等的，但是j肯定指向povit的前一个元素
        if (j >= k) return quick_select(nums, left, j, k);
        else return quick_select(nums, j + 1, right, k);
    }

    int findKthLargest(vector<int>& nums, int k) {
        return quick_select(nums, 0, nums.size() - 1, k - 1);
    }
};