数组中第K大的元素

利用快排中的Partition
算法导论中经典的partition

class Finder {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        return findK(a, 0, n-1, K);
    }
    int findK(vector<int> &a, int L, int R, int K){
        int mid = partition(a, L, R);
        int nRight = R - mid + 1;
        if(K == nRight){
            return a[mid];
        }else if(K > nRight){
            return findK(a, L, mid - 1, K - nRight);
        } else{
            return findK(a, mid + 1, R, K);
        }
    }
    int partition(vector<int> &a, int L, int R){
        int v = a[R];
        int j = L-1;
        for(int i = L; i <= R; i++){
            if(a[i] <= v){
                j++;
                swap(a[i], a[j]);
            }
        }
        return j;
    }
};