题解 | #寻找第K大#

class Solution {
public:
    int partition(vector<int> &a, int left, int right){
        int first = a[left];
        while(left < right){
            while(left < right && first >= a[right]){
                right --;
            }
            if(first < a[right]){
                a[left++] = a[right];
            }
            while(left <right && a[left] >= first){
                left ++;
            }
            if(a[left] < first){
                a[right--] = a[left];
            }
        }
        a[left] = first;
        return left;
    }
    int quickSort(vector<int> &a, int left, int right, int K){
        int pos = partition(a, left, right);
        if(pos == K-1) return a[K-1];
        else if(pos < K-1){
            return quickSort(a, pos+1, right, K);
        }else{
            return quickSort(a, left, pos-1, K);
        }
    }
    int findKth(vector<int> a, int n, int K) {
        int res = quickSort(a, 0, n-1, K);
        return res;
    }
};