查找數組中第k大的數算法代碼

問題：
查找出一給定數組中第k大的數。例如[3,2,7,1,8,9,6,5,4]，第1大的數是9，第2大的數是8……

思路：
1. 直接從大到小排序，排好序後，第k大的數就是arr[k-1]。
2. 只需找到第k大的數，不必把所有的數排好序。我們借助快速排序中 partition過程，一般情況下，在把所有數都排好序前，就可以找到第k大的數。我們依據的邏輯是，經過一次partition後，數組被pivot 分成左右兩部分：S左、S右。當S左的元素個數|S左|等於k-1時，pivot即是所找的數；當|S左|小於k-1，所找的數位於S右中；當|S 左|>k-1，所找的數位於S左中。顯然，後兩種情況都會使搜索空間縮小。

代碼：

int Partition(int *arr, int from, int to)
{
    int i, j;
    i = j = from;
    while (j <= to)
    {
        if (arr[j] >= arr[to]) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
        }
        j++;
    }
    return i - 1;
}
int quickSelect(int *s, int k, int left, int right)
{
    if (left == right) return s[left];
    int i;
    i = Partition(s, left, right);
    if (i - left + 1 == k) {
        return s[i];
    }
    else if (i - left + 1 < k) {
        return quickSelect(s, k - (i - left + 1), i + 1, right);
    }
    else return quickSelect(s, k, left, i - 1);
}
int findKthLargest(int* nums, int numsSize, int k) {
    return quickSelect(nums, k, 0, numsSize - 1);
}

至於”查找數組中第k小的數“，那自然可以舉一反三，同樣處理了。