题解 | 寻找第K大

class Solution {
public:
  //完整快速排序后，第K大的数一定在K-1的下标处；
  //利用二分法， 减少处理；
    int findKth(vector<int>& a, int n, int K) {
        return quikSelect(a, 0, n-1, K-1);
    }

    int quikSelect(vector<int>& a, int left, int right, int k){
        if(left == right) return a[left];

        int pivotIndex = partition(a, left, right);

        if(pivotIndex == k){
            return a[pivotIndex];
        }else if(pivotIndex > k){
            return quikSelect(a, left, pivotIndex-1, k);
        }else if(pivotIndex < k){
            return quikSelect(a, pivotIndex+1, right, k);
        }

        return -1;
    }

    int partition(vector<int>& a, int left, int right){  //快速排序
        int pivot = a[right];
        int i=left;

        for(int j=left; j<right; ++j){
            if(a[j] > pivot){
                swap(a[i], a[j]);
                ++i;
            }
        }

        swap(a[i], a[right]);
        return i;
    }
};