桶外排序算法的抽样分点分发策略

• 作者: 宋涛 杨磊 黄辉
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 外排序 桶排序 多路归并 分发策略 抽样分点 PennySort
• 年，卷（期）: 2005,（5）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 643-651
• 页数: 9页
• 分类号: TP301
• 字数: 5570字
• 语种: 中文

摘要

计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以上问题,扩展桶排序的应用范围.讨论了抽样分点估计的收敛性,给出了不发生内存溢出的保证概率.该策略使桶排序算法在SheenkSort排序系统上得到成功应用,并最终获得2003年度PennySort世界排序比赛Indy组冠军.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨磊	清华大学计算机科学与技术系	14	147	7.0	12.0
2	黄辉	中联绿盟信息技术(北京)有限公司开发部	1	8	1.0	1.0
3	宋涛	清华大学计算机科学与技术系	4	44	4.0	4.0