成都金堂县五月花学校:这个算法,不明白,有人能来讲讲么,谢谢~
来源:百度文库 编辑:神马品牌网 时间:2024/08/28 10:04:40
算法4 Select(S,k) 改进的算法
1.将S划分成5个一组, 共nM=[n/5]个组
2.每组找中位数,nM个中位数放到集合M
3.m*←Select(M,|M|/2) 将S中的数划分成A,B,C,D四个集合
4.把A和D中的每个元素与m*比较,小的构成S1, 大的构成S2
5.S1←S1∪C; S2←S2∪B
6.if k =|S1|+1 then 输出m*
7.else if k≤|S1|
8. then Select(S1,k)
9. else Select(S2,k-|S1|-1)
1.将S划分成5个一组, 共nM=[n/5]个组
2.每组找中位数,nM个中位数放到集合M
3.m*←Select(M,|M|/2) 将S中的数划分成A,B,C,D四个集合
4.把A和D中的每个元素与m*比较,小的构成S1, 大的构成S2
5.S1←S1∪C; S2←S2∪B
6.if k =|S1|+1 then 输出m*
7.else if k≤|S1|
8. then Select(S1,k)
9. else Select(S2,k-|S1|-1)
sad