一个拟就地稳定归并排序算法-论文.pdf

《一个拟就地稳定归并排序算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第27卷第2期湖南理工学院学报(自然科学版)VO1．27NO．22014年6月JournalofHunanInstituteofScienceandTechnology(NaturalSciences)Jun．2014一个拟就地稳定归并排序算法胡圣荣(华南农业大学￡程学院，广州510642)摘要：为了降低经典归并排序算法O(n)的附加空间并保持稳定性，提出一个新的拟就地归并算法．介绍了根据移动次数导出的段长关系进行选择的原理，给出了相应的归并及归并排序的C语言算法，用大量随机序列进行了排序对比测试

2、；测试组数自动选取，拟合结果为比较次数约为0．13nln)+1．24nln(n)一1．22n，移动次数约为0．655nln(n)～0．89nIn(n)+2．6月、附加栈空间O(In(，z))．得益于算法的简便性，附加程序开销小，在测试范围内实际时空耗费在同类算法中有明显优势．关键词：归并；就地归并；归并排序：算法中图分类号：TP311．12文献标识码：A文章编号：1672．5298(2014)02—0045．05AStableIn—situMergeSortAlgorithmHUSheng．ron

3、g(CollegeofEngineering，SouthChinaAgriculturalUniversity,Guangzhou510642，China)Abstract：InordertoreducetheO(n)additionalspaceofclassicalmergesortandkeepstability,anewin—situmergingalgorithmispresented．Thelengthprinciplederivedfromthemobilenumberofassig

4、nmentsisintroduced．CorrespondingmergesortinClanguagewastestedbygroupsofrandomsequences，thenumberofgroupsisalsochosenautomatically．Resultsshowthatthenumberofcomparisonsisabout0．13nIn(n)+1．24nln(n)一1．22n，thenumberofassignmentsisabout0．655nIn(n)一0．89nIn(

5、n)+2．6n，theadditionalstackspaceisO(In(n))benefitingbysimplicityandlowadditionalprogramcost，thealgorithmpresentedexhibitsaclearadvantageinbothpracticaltimeandspaceconsumingcomparedwithaneficientmergesortalgorithm．Keywords：merge；in—placemerge；mergesort；

6、algorithm引言排序是计算机理论和实际应用中的一个基本问题，目前已有众多排序算法，但一些新算法仍在不断现，主要是因为各种算法都有其优缺点，很难在各种情况下都表现良好．对排序算法，通常会关心关键字的比较次数、移动次数、稳定性、附加空间以及实际执行时间等．比如有的算法较快但需要一定的附加空间；有的算法虽然比较次数、移动次数较少，但实际性能不佳，因为除了比较、移动，还有大量其它附加操作．在经典的基于比较的排序算法中，比较次数至少需要log!nlog：n一1．443n，移动次数下限为I，21．时19

7、复杂度等于或接近O(nlog2)的算法除MergeSort外，QuickSort、HeapSort、ShellSort等均是不稳定的．但经典归并排序需要O(n)的附加空间，为此许多文献研究附加空间小的直至理想的就地归并排序，其核心是归并算法．这方面一个常用的方法或技巧是“内部缓存”技术I2'，较典型的结果如Oefert等的稳定算法最多m(，+1)+n+O(m)次比较，5n+12m+O(m)次移动J，其中m≤，z，=Llog(告)j．然而为追求线性时间、稳定性、就地进行，很多归并算法相当复杂，即便有

8、理论k的渐进线性复杂性，但较大的线性因子及复杂的结构，并不适合归并排序．也有些算法丢弃了稳定性，如文【4]．若放松严格的收稿日期：2014．03—28作者简介：胡荣(1967一)，男，湖北天门人，博士，华南农业大学ll：程学院教授．主要研究方向：计算机数值算法湖南理T学院学报(自然科学版)第27卷“就地”要求，允许O(1og：，z)的附加栈空间，则算法可以简洁些，如文[5]，文献中常称为“in—situ”，为了区别“in—place”，本文称这种情况为“拟就地”的(也有的文献用“m