[数据结构与算法]LeetCode.数组中的第k个最大的元素（基于快速排序的选择排序算法）

?题目描述：来自LeetCode

?思路：快速排序的时间复杂度是O(NlogN)，但是基于快速排序的选择排序算时间复杂度只有O（N)。快速排序：就是找到一个枢轴，将枢轴左边比枢轴大的数都移动到枢轴右边，枢轴右边比枢轴小的数移到枢轴左边，再对左边和右边分别用同样的方法排序，最后得到一个有序的数组。而快速选择找到第k大的数或者第k小的数，我们并不用每次都将两边排序，我们只用排序k所在的一边就行。比如说第一次排序之后，数组左边的数一定全部小于右边，即使我们再对左边和右边进行排序，在左边的数还是在左边，在右边的数还是在右边，也就是说每次排序，我们都能通过k这个下标来确定k在左边还是右边，那我们每次排序k所在的一边就行了，至于另一边是否有序，都对结果没有影响。举个例子 [1 4 3 7 2]，k=2，找第k小的数，第一次排序后[1 2 3 7 4],k=2，下标2-1=1（因为从0开始存，第k小的数在数组位置是k-1）位于枢轴mid=2的左边，那我们就只用排序左侧,就可以找到第k小的数啦。

快速排序使用两个指针，初始时指针指向数组两侧不是数组第一个和最后一个哦，因为我们用的do-while，递归结束的条件就是两个指针指向同一个位置。

这道题是求第k个最大的元素，跟求第k个最小的数原理一样，只不过求第k大用递减排序，求第k小用递增排序

int findKthLargest(vector<int>& nums, int k) {
        int n=nums.size();
        return quick_select(0,n-1,nums,k-1);
    }
    int quick_select(int l,int r,vector<int>& nums,int k){
        if(l==r) return nums[l];
        int i=l-1,j=r+1;
        int mid=nums[(l+r)>>1];
        while(i<j){
            do i++;while(nums[i]>mid);
            do j--;while(nums[j]<mid);
            if(i<j) swap(nums[i],nums[j]);
        }
        if(k<=j) return quick_select(l,j,nums,k);
         return quick_select(j+1,r,nums,k);
    }

今日刷题任务完成，如有错误，欢迎指正~