资源描述：
《桶外排序算法的抽样分点分发策略》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1000-9825/2005/16(05)0643©2005JournalofSoftware软件学报Vol.16,No.5∗桶外排序算法的抽样分点分发策略1+21杨磊,黄辉,宋涛1(清华大学计算机科学与技术系,北京100084)2(中联绿盟信息技术(北京)有限公司开发部,北京100089)TheSample-SeperatorsBasedDistributingSchemeoftheExternalBucketSortAlgorithm1+21YANGLei,HUANGHui,SONGTao1(DepartmentofComputerSciencea
2、ndTechnology,TsinghuaUniversity,Beijing100084,China)2(DepartmentofDevelopment,NSFOCUSInformationTechnologyCo.,Ltd.,Beijing100089,China)+Correspondingauthor:Phn:+86-10-62777918,E-mail:yanglei@sheenk.com,http://www.tsinghua.edu.cnReceived2004-03-23;Accepted2004-06-11YangL,HuangH,S
3、ongT.Thesample-seperatorbaseddistributingschemeoftheexternalbucketsortalgorithm.JournalofSoftware,2005,16(5):643−651.DOI:10.1360/jos160643Abstract:TwowaystosortexternallyareMulti-LineMergingSortandBucketSort,bothwithtwopasses.TheBucketSortburdenstheCPUlessandismoreefficient,whil
4、eitsusageisrestrictedheavilybytheHigh-Bitschemethatdistributesrecordsintosubfiles:thekeyshavetobeintegers;thesizesofsubfilesmayvarytoomuch;thenumberofsubfilescannotbechosenfreely.Basedonstatisticaltheory,thispaperpresentsasample-seperatorsschemetobroadentheussageofbucketsortalgo
5、rithm.Abriefdiscussionontheconverganceofsample-seperatorestimationisgivenandtheprobabilitytoavoidmemoryoverflowiscalculated.ThisschemeenablesthebucketsortalgorithmtobeappliedintheSheenkSortsystemtowinthe2003PennySort(theIndycategory)competition.Keywords:externalsort;bucketsort;m
6、ulti-linemerging;distributingscheme;sample-separators;PennySort摘要:计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以上问题,扩展桶排序的应用范围.讨论了抽样分点估计的收敛性,给出了不发生内存溢出的保证概率.该策略使桶排序算法在SheenkSort排序系统上得到成功应用,并最终获得2003年度PennySort世界排序
7、比赛Indy组冠军.关键词:外排序;桶排序;多路归并;分发策略;抽样分点;PennySort中图法分类号:TP301文献标识码:A∗SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNos.60223004,60321002,60303005(国家自然科学基金)作者简介:杨磊(1978－),男,湖北武汉人,博士生,主要研究领域为计算机人工智能;黄辉(1978－),男,主要研究领域为计算机网络安全及应用;宋涛(1978－),男,博士生,主要研究领域为计算机信息安全.644Jour
8、nalofSoftware软件学报2005,16(5)排序问题是计算机领域十分基础而重要的问题
