思考题

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的权值和，是否满足题目中的公式

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

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

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

邮局位置问题：

关键是d)的结论

9-3 小型顺序统计量

？？？