Quick select

我們要從 array 裡找第 k 大的數時，可以用 quick select

一定要注意題意，第 k 大不是第 k 個....所以可以傳第 array.length - k 大的參數

這樣就可以用跟 quick sort 一樣的方式

也就是 quick sort 的 partition部分，

為什麼呢？因為當我們選定一個 pivot時，去做左右分堆，那麼 pivot 左邊一定都比 pivot 小，

所以當分完堆之後看看 pivot 的位置是不是 k，如果是就找到了第 k 大的數

比 k 小那我們往左邊繼續找

// pass A.length - k as k
public int quickSelect(int[] A, int start, int end, int k) {
    if (start >= end) {
        return A[k];
    }

    int left = start, right = end;
    int pivot = A[(start+end)/2];

    while (left <= right) {
        while (left <= right && A[left] < pivot) {
            left++;
        }
        while (left <= right && A[right] > pivot) {
            right--;
        }
        if (left <= right) {
            int temp = A[left];
            A[left] = A[right];
            A[right] = temp;
            left++;
            right--;
        }
    }

    if (k <= right)
        return quickSelect(A, start, right, k);
    if (k >= left)
        return quickSelect(A, left, end, k);
    return A[k];
}