桶外排序算法的抽样分点分发策略
The Sample-Seperators Based Distributing Scheme of the External Bucket Sort Algorithm作者机构：清华大学计算机科学与技术系北京100084 中联绿盟信息技术(北京)有限公司开发部北京100089
出 版 物：《软件学报》 (Journal of Software)
年 卷 期：2005年第16卷第5期
页 面：643-651页
核心收录：
学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）]
基 金：国家自然科学基金~~
主 题：外排序 桶排序 多路归并 分发策略 抽样分点 PennySort
摘 要：计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以上问题,扩展桶排序的应用范围.讨论了抽样分点估计的收敛性,给出了不发生内存溢出的保证概率.该策略使桶排序算法在SheenkSort排序系统上得到成功应用,并最终获得2003年度PennySort世界排序比赛Indy组冠军.
维普期刊数据库
同方期刊数据库