共 3 条
桶外排序算法的抽样分点分发策略
被引：5
作者：
杨磊
黄辉
宋涛
机构：
[1] 清华大学计算机科学与技术系
[2] 中联绿盟信息技术(北京)有限公司开发部
[3] 清华大学计算机科学与技术系 北京
[4] 北京
来源：
关键词：
外排序;
桶排序;
多路归并;
分发策略;
抽样分点;
PennySort;
D O I：
暂无
中图分类号：
TP311.12 [];
学科分类号：
081202 ;
0835 ;
摘要：
计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以上问题,扩展桶排序的应用范围.讨论了抽样分点估计的收敛性,给出了不发生内存溢出的保证概率.该策略使桶排序算法在SheenkSort排序系统上得到成功应用,并最终获得2003年度PennySort世界排序比赛Indy组冠军.
引用
收藏
页码：643 / 651
页数：9
相关论文