/* * 返回数组A[p...r]中第i个小的元素, O(n)， * 使用快速排序的思想。 * */ 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 randomized_select(A, p, q, i); else return randomized_select(A, q+1, r, i-k); }
转载于:https://www.cnblogs.com/prajna/archive/2013/03/02/2940500.html
