c++ 快排+二分

思路：快排+二分法
像快排一样，但是每次排完需要与k进行比较，具体比较看代码。
1.由于一般排序是从小到大排的；
所以注意这里比较的时候是 n-i 与 k进行比较；
2.或者从大到小排，则比较 i+1 与 k的大小；

代码：

1. 从小到大排序：

class Finder {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        return quick_sort(a, 0, n - 1, n, K);
    }

    int quick_sort(vector<int>& a, int start, int end, int n, int k) {
        int base = a[start];
        int i = start;
        int j = end;
        int res = 0;

        while (i < j) {
            while (i<j && a[j]>=base) --j;
            while (i<j && a[i]<=base) ++i;
            if (i < j) swap(a[i], a[j]);
        }
        swap(a[start], a[j]);

        if (n - j == k) return a[j];
        else if (n - j < k) res = quick_sort(a, start, j-1, n, k);
        else if (n - j > k) res = quick_sort(a, j+1, end, n, k);
        return res;
    }
};

2. 从大到小排序：

class Finder {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        return quick_sort(a, 0, n - 1, n, K);
    }

    int quick_sort(vector<int>& a, int start, int end, int n, int k) {
        int base = a[start];
        int i = start;
        int j = end;
        int res = 0;

        while (i < j) {
            while (i < j && a[j] <= base) --j;
            while (i < j && a[i] >= base) ++i;
            if (i < j) swap(a[i], a[j]);
        }
        swap(a[start], a[i]);

        if (i+1 == k) return a[i];
        else if (i+1 > k) res = quick_sort(a, start, i-1, n, k);
        else if (i+1 < k) res = quick_sort(a, i+1, end, n, k);
        return res;
    }
};