《算法导论》第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。