题解 | #寻找第K大#

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        quicksort(a,0,n-1,K);
        return a[K-1];
    }
    int partition(vector<int> &a,int left, int right)
    {
        int r=rand()%(right-left)+left,tmp=a[r];
        a[r]=a[left];
        a[left]=tmp;
        while(left<right)
        {
            while(left<right&&a[right]<=tmp)
                right--;
            if(left<right)
                a[left++]=a[right];
            while(left<right&&a[left]>=tmp)
                left++;
            if(left<right)
                a[right]=a[left];
        }
        a[left]=tmp;
        return left;
    }
    void quicksort(vector<int> &a, int left,int right, int k)
    {
        if(left>=right)
            return ;
        int mid=partition(a,left,right);
        if(mid==k-1)
            return ;
        if(mid<k-1)
            quicksort(a,mid+1,right,k);
        else 
            quicksort(a,left,mid-1,k);
    }
};

快排，通过每层快排返回的索引与K-1对比，判断需排序的数