基于数组的桶排序算法.pdf

《基于数组的桶排序算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、计算机研究与发展lSSN1000-1239!CN11-1777!TPJournalofComputerResearchanddevelopment44（2）：341"347，2007!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!基于数组的桶排序算法杨磊宋涛（清华大学计算机科学与技术系北京100084）（yanglei96#mails.tsinghua.edu.cn）Thearray-basedbucketSortal

2、gorithmYangLeiandSongTao（DePartmentofComPuterscienceandtechnology，tsinghuaunioersity，Beijing100084）abstractClassicalbucketsortalgorithmimplementsbucketsasdynamiclists.ltsortsuniformdataefficientlyWithin0（N）timebutdegradestotheinefficient0（N2）insertio

3、nsortWhenhandlingextremely-nonuniformdata.ByanalyZingcountingsortWithextradata，amethodispresentedtoimplementthebucketsasseCuentialarrays.Theefficiencyisimproveddirectlybyavoidingthecomplexoperationsofdynamicmemoryallocation.furthermore，0（NlogN）algori

4、thmslikeCuicksortmaybeemployedtomanageeachbucket.ThecomposedalgorithmstillsortsuniformdataWithin0（N）timebutsimplydegradestotheoriginal0（NlogN）algorithmintheWorstcase.lngeneralcase，itisprovedthatthecomposedbucketsortalgorithmalWaysachievesbetterperfor

5、mance.experimentsonuniformdatashoWthesuperioritiesofthebucketsortalgorithms，andthatthearray-basedbucketsortalgorithmbeatstheclassicalalgorithm.lnexperimentsWithGaussiandata，thenon-uniformityinfluencesthearray-basedalgorithmmuchlessthantheclassicalalg

6、orithmWherebothoutperformtheCuicksort.Keywordscomplexity；sortingalgorithm；countingsort；bucketsort；Cuicksort；PennySort摘要经典桶排序算法以链表形式实现“桶”，处理均匀数据效率很高，是0（N）算法.但对极不均匀数据则退化成低效的0（N2）插入排序.讨论了记录携带附加数据的计数排序算法，将“桶”实现为顺序数组，避免链表的动态内存分配直接提高算法效率，并允许快排等0（NlogN）算法处理

7、桶内数据.对均匀数据仍然保持0（N）时间复杂度，对极端不均匀数据则只退化为0（NlogN）的原算法.对一般非均匀数据，证明数组桶排序算法总体性能高于经典算法.均匀数据实验表明，桶排序算法明显优于Linux下标准Csort系统调用，且数组桶排序算法效率更高.而在非均匀的正态数据实验中数组桶算法性能下降明显小于经典桶排序，总体效率仍然优于Csort的直接应用.关键词复杂度；排序算法；计数排序；桶排序；快速排序；PennySort中图法分类号TP301.6排序是计算机领域中一类非常重要的问题，在种排序

8、算法如冒泡排序［3］、快速排序［4］等.近几年计算机科学与技术中经常遇到，在很多数据处理中的研究又提出了分段快速排序［5］、基数链接排也占用了计算机大量的处理时间.有效的排序算法序［6］、分片扩展排序［7］等算法.一直是人们感兴趣的问题［1-2］.过去人们提出了各但两类排序算法却很少提及计数排序和桶排收稿日期：2005-09-14；修回日期：2006-05-24基金项目：国家“九七三”重点基础研究发展规划基金项目（2004CB318108）；国家自然科学基金项目（60223004，6032100