作业6.选第k小元素：特定分治策略
实验报告
- 问题
在给出的n个数中，找到第k小的数。
2.解析
以S中的某个元素m作为划分标准，将S划分为两个子数组S1和S2，把这个数组中比m小的都放入S1的数组中，数组S1的元素个数是|S1|个；把这个数组中比m*大的都放入S2的数组中，数组S2的元素个数是|S2|个。
若k<|S1|，则原问题归纳为在数组S1中找第k小的子问题。
若k=|S1|+1，则m*就是要找的第k小元素。
若k>|S1|+1，则原问题归纳为在数组S2中找第n−|S1|−1小的子问题
3.设计
令q=[p/5]（向下取整）。将A分成q组，每组5个元素。如果5不整除p，则排除剩余元素
将q组中的每一组单独排序，找出中项。所有中项的集合为M
m* ← select(M, 1, q, [q/2]（向上取整）) {m*为中项集合的中项}
将A[low…high]分成三组 A1 = {a|a<m*} A2 = {a|a=m*} A3 = {a|a>m*}
case
|A1|>=k: return select(A1, 1, |A1|, k)
|A1|+|A2|>=k: return m*
|A1|+|A2|<k: return select(A3, 1, |A3|, k-|A1|-|A3|)
4.分析
5.源码
https://github.com/cyy1176489683/Design-and-analysis-of-algorithms/tree/master/homework6