在一個(gè)由n個(gè)元素組成的集合中，第i個(gè)順序統(tǒng)計(jì)量是該集合中第i小的元素残黑。例如斋否，在一個(gè)元素集合中，最小值是第1個(gè)順序統(tǒng)計(jì)量(i=1),最大值是第n個(gè)順序統(tǒng)計(jì)量疫诽。
假設(shè)集合中的元素都是互異的旦委，但可以推廣到集合中包含重復(fù)元素的情形缨硝。
輸入：一個(gè)包含n個(gè)（互異的）數(shù)的集合A和一個(gè)整數(shù)i，1≤i≤n查辩。
輸出：數(shù)組中的元素x，且A中恰好有i-1個(gè)元素小于它长踊。
可以在O(nlgn)時(shí)間內(nèi)解決這個(gè)選擇問題，因?yàn)榭梢杂枚雅判蚧驓w并排序?qū)斎霐?shù)據(jù)進(jìn)行排序辟汰，然后在輸出數(shù)組中根據(jù)下標(biāo)找到第i個(gè)元素即可阱佛。
最大值和最小值
MINIMUM(A)
min = A[1]
for i = 2 to A.length
if min > A[i]
min = A[i]
return min
為了確定最小值瘫絮，必須要做n-1次比較麦萤。因此扁眯，從所執(zhí)行的比較次數(shù)來看，算法MINIMUM是最優(yōu)的命满。
同時(shí)找到最小值和最大值 可以分別獨(dú)立地找出最大值和最小值胶台，這各需要n-1次比較杂抽，共需2n-2次比較。事實(shí)上缩麸，只需要最多次比較就可以同時(shí)找到最小值和最大值杭朱。具體的方法是記錄已知的最小值和最大值。但我們并不是將每一個(gè)元素與當(dāng)前的最大值和最小值進(jìn)行比較-這樣做的代價(jià)是每個(gè)元素需要2次比較八酒，而是對(duì)輸入元素成對(duì)地進(jìn)行處理丘跌。首先，我們將一對(duì)輸入元素相互進(jìn)行比較闭树，然后把較小的與當(dāng)前最小值比較，把較大的與當(dāng)前最大值進(jìn)行比較报辱。這樣碍现，對(duì)每對(duì)元素共需3次比較。
如果n為奇數(shù)爽篷，我們將最大值和最小值的初值都設(shè)為第一個(gè)元素的值慢睡，然后成對(duì)地處理剩下的元素漂辐。如果n是偶數(shù)，就對(duì)前兩個(gè)元素進(jìn)行一次比較袒啼，以決定最大值和最小值的初值蚓再，然后成對(duì)地處理余下的元素对途。
期望時(shí)間為線性時(shí)間的選擇算法
一般選擇問題看起來要比找最小值這樣的簡(jiǎn)單問題更難。但令人驚奇的是实檀，這兩個(gè)問題的漸近運(yùn)行時(shí)間卻是相同的:Θ(n)膳犹。
以快速排序算法為模型须床，將輸入數(shù)組進(jìn)行遞歸劃分渐裂。但與快速排序不同的是，快速排序會(huì)遞歸處理劃分的兩邊族阅，而RANDOMIZED-SELECT只處理劃分的一邊。RANDOMIZED-SELECT的期望運(yùn)行時(shí)間為Θ(n)愧沟。這里沐寺，假設(shè)輸入數(shù)據(jù)都是互異的混坞。
RANDOMIZED-SELECT(A, p, r, i)
if p == r
return A[p]
q = RANDOMIZED-PARTITION(A, p, r)
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)
最壞情形運(yùn)行時(shí)間為Θ(n2)钢坦。
期望運(yùn)行時(shí)間為O(n)，假設(shè)元素是互異的。
最壞情形為線性時(shí)間的選擇算法
- 將輸入數(shù)組的n個(gè)元素劃分為
組逛万，每組5個(gè)元素宇植，且至多只有一組由剩下的n mod 5個(gè)元素組成。
- 尋找這
- 對(duì)第2步中找出的
- 利用修改過的PARTITION版本闲坎，按中位數(shù)的中位數(shù)x對(duì)輸入數(shù)組進(jìn)行劃分。讓k比劃分的低區(qū)中的元素?cái)?shù)目多1茬斧，因此x是第k小的元素腰懂，并且有n-k個(gè)元素在劃分的高區(qū)。
- 如果i=k项秉，則返回x绣溜。如果i<k，則在低區(qū)遞歸調(diào)用SELECT來找出第i小的元素娄蔼。如果i>k,則在高區(qū)遞歸查找第i-k小的元素底哗。
