寻找数组中第k小的元素

KthNumber.cpp

int quickSelect(vector<int> &nums, int k) {
    int lo = 0;
    int high = (int)nums.size() - 1;
    for(; lo < high; ) {
        int i = lo, j = high;
        int pivot = nums[lo];
        while(i < j) {
            while( i < j && pivot <= nums[j]) {
                j--;
            }
            nums[i] = nums[j];
            while(i < j && pivot >= nums[i]) {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = pivot;
        if (k <= i) {
            high = i - 1;
        }
        if (i <= k) {
            lo = i + 1;
        }
    }
    return nums[k-1];
}