這一節(jié)講解與排序相關(guān)又不同的問題
順序統(tǒng)計(jì)（Order Statistics），引申出中值的算法

順序統(tǒng)計(jì)

有一系列的元素n在數(shù)組中（無序），希望找到第k小的數(shù)

原始的方案：對數(shù)組排序，并返回第k位元素，T(n) = O(nlgn)，我們希望找到比這個(gè)更好的方法，即線性時(shí)間

這個(gè)問題有許多應(yīng)用
如果k=1 => 最小值
如果k=n => 最大值
如果k=n/2 => 中值，也就是這節(jié)課的重點(diǎn)

隨機(jī)分治算法
random-select(A, p, q, i) | i代表第i小的元素，A元素?cái)?shù)組，p\q為查找區(qū)間

if p=q then 
    return A[p]
r = random-select(A, p, q)       | 快速排序的方法
k = r-p+1                        | 劃分元素的序號
if i=k then return A[r]
if i<k then 
    return random-select(A, p, r-1, i)
if i>k then
    return ramdom-select(A, r-1, q, i)

random-select

舉個(gè)例子

算法分析（分析前提：元素不想等）

直覺分析
Lucky Case: 如果每次都是1/10和9/10劃分
T(n) = T(9/10 n) + Θ(n) | 滿足主方法情況三
T(n) = Θ(n)
Unlucky Case: 每次都劃分成0和n-1
T(n) = T(n-1) + Θ(n) = Θ(n²)
可以使用與隨機(jī)快速排序相同的方法，每次隨機(jī)選擇主元(pivot)

數(shù)學(xué)分析（略）

線性的最壞情況隨機(jī)選擇worst-case linear-time randomized select
select算法：
把數(shù)組按每5個(gè)進(jìn)行分組，得到5/n個(gè)子數(shù)組
對每個(gè)子數(shù)組進(jìn)行排序，得到每一組的中值 | Θ(n)
遞歸的對中值計(jì)算中值 | T(n/5)
按中位數(shù)的中位數(shù)x進(jìn)行分區(qū)劃分，x作為第k小的元素，n-k個(gè)元素在高位區(qū)
如果i=k，返回x
如果i<k，在低區(qū)遞歸調(diào)用select找到第i小的元素
如果i>k，在高區(qū)遞歸找到第i-k個(gè)最小元素