《算法導論》第9章 順序統計學 (2)随機選擇

randomized_select使用劃分方法randomized_partition()，傳回主元位置q（第k小元素）。

要查找的是第 i 小元素，若恰好等于k，那麼直接傳回。

如果 i < k，則繼續在[p, q - 1]中搜尋第 i 小元素。

如果 i > k，則繼續在[q + 1, r]中搜尋第 i - k 小元素。

int randomized_select(int A[], int p, int r, int i)

{

if (p == r)

return A[p];

int q = randomized_partition(A, p, r);

int k = q - p + 1;

if (i == k)

return A[q];

else if (i < k)

return randomized_select(A, p, q - 1, i);

else

return randomized_select(A, q + 1, r, i - k);

}

int main(void)

int A[] = { 2, 8, 9, 13, 4, 7, 11 };

int ret = randomized_select(A, 0, 6, 2);

printf("%d\n", ret);

例如，randomized_partition執行後數組A為：2, 4, 7, 8, 11, 9, 13。

元素8是主元，q = 3，即8是第4小的元素。要查找的是第 i = 2 小元素。

則繼續在[2, 4, 7]中查找第2小元素。

假如要查找的是第6小元素，則在[11, 9, 13]查找第2（6 - 4）小元素，即7。