Question

9-1 已排序的 i 个最大数

a）合并排序和堆排序,O(nlgn)
b）堆排序,O(n+ilgn)
c）快速排序,O(n+ilgi)

9-2 带权中位数

b）

使用最坏情况时间为 O(nlgn) 的排序算法对每个元素进行排序

依次累加元素的权重，直到满足题目中公式

c）

step1：利用 SELECT 中寻找中值的中值的算法，找到主元

step2：用主元把数组分为三段，即 A[1..q-1] < A[q] < A[q+1..r]

step3：计算 A[1..q-1]<0.5 和 A[1..q]>=0.5 的权值和，是否满足题目中的公式

step4：若满足，A[q]就是所求的数

step5：若不满足，就继续递归使用本算法进行递归查找。偏大就找前半段，偏小就找后半段

代码见 算法导论-9-2-c-带权中位数

邮局位置问题：

关键是 d) 的结论

9-3 小型顺序统计量

a）待解决