期望為線性時間的選擇演算法

將輸入數組進行遞歸劃分，只遞歸調用一邊，

假設數組A[p..r]中的元素都不同，返回數組A中第i小的元素，

Partition(A,p,r)x = A[r]i = p -1for j = p to r-1 if A[j] <= x i = i + 1 exchange A[i] with A[j]exchange A[i] with A[j]return i+1Randomization-Partition(A,p,r)i = __RANDOM(p,r)exchange A[i] with A[r]return Partition(A,p,r)Randomized-select(A,p,r,i)if p == r return A[p]q = Randomized-Parition(A,p,r)k = q - b + 1if 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)

推薦閱讀：