MIT算法导论六 顺序统计和中值

这一节讲解与排序相关又不同的问题
顺序统计（Order Statistics），引申出中值的算法

顺序统计

有一系列的元素n在数组中（无序），希望找到第k小的数

原始的方案：对数组排序，并返回第k位元素，T(n) = O(nlgn)，我们希望找到比这个更好的方法，即线性时间

这个问题有许多应用
如果k=1 => 最小值
如果k=n => 最大值
如果k=n/2 => 中值，也就是这节课的重点

随机分治算法
random-select(A, p, q, i) | i代表第i小的元素，A元素数组，p\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

举个例子

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

直觉分析
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²)
可以使用与随机快速排序相同的方法，每次随机选择主元(pivot)

数学分析（略）

线性的最坏情况随机选择worst-case linear-time randomized select
select算法：
把数组按每5个进行分组，得到5/n个子数组
对每个子数组进行排序，得到每一组的中值 | Θ(n)
递归的对中值计算中值 | T(n/5)
按中位数的中位数x进行分区划分，x作为第k小的元素，n-k个元素在高位区
如果i=k，返回x
如果i<k，在低区递归调用select找到第i小的元素
如果i>k，在高区递归找到第i-k个最小元素