一种4路插入排序算法.pdf

《一种4路插入排序算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、·76·工业仪表与自动化装置2013年第6期一种4路插入排序算法王昱，杨小萍，陈延文，李德录(天水师范学院物理与信息科学学院，甘肃天水741000)摘要：提出了一种4路插入排序算法，给出了算法思想及其实现，与传统循环2路插入排序算法相比，该算法在空间复杂度相同的情况下，平均时间效率得到了提高。关键词：数据结构；4路插入排序；算法中图分类号：TP311．1文献标志码：A文章编号：1000—0682(2013)06—0076—04A4．．wayinsertionsortalgorithmWANGYu，YANGXiaoping，CHENYanwen，LIDelu(SchoolofPhysi

2、csandlnfbrmationScience，TianshuiNormalUniversity，GansuTianshui741001，China)Abstract：A4一wayinsertionsortalgorithmisproposedwithanintroductionofitsalgorithmprinci—pieandimplementation．Theaveragetimeeficiencyofthe4一wayinsertionsortalgorithmisimprovedunderthesamespacecomplexity，comparedtotheorigina

3、lcircular2一wayinsertionsortalgorithm．Keywords：datastructure；4一wayinsertionsort；algorithm0引言1算法思想传统循环2路插入排序算法是对直接插入排设待排序的一组数据记录存放在顺序表L．r序算法的一种改进。由于额外开辟了n个数据记录[0]～L．r[2n一1]中的前n个存储单元中，即L．r的辅助空间(与待排序顺序表同类型的数组，并将[0]～L．r[n一1]中，要求依关键字值从小到大(即其看作一个循环向量)，所以空间复杂度为0(n)。关键字值非递减)进行排序。尽管其时问复杂度与直接插入排序算法的相同，仍首先

4、，对顺序表L．r的前4个数据记录依关键字然是0(n)，但在数据记录随机的情况下，由于减少值从小到大进行排序(即L．rE0]～L．r[3]，可采用直接了关键字的平均比较次数和数据记录的平均移动次插入排序法)，然后将L．r[1]转存于L．r[n]中、L．rE2]数，所以其平均时间效率比直接插入排序算法得到转存于L．r[n+1]中、L．r[3]转存于L．r[2n一1]中，了提高。这样就在顺序表L．r[0]～L．r[2n一1]中的前部、中该文提出了一种4路插入排序算法，对于待排部、后部形成了4个只含有一个记录的有序表L．rE0]序的n个数据记录，开辟2n个数据记录的连续存储～L．r[0]、L

5、．r[n]～L．r[n]、L．r[n+1]～L．r[n+1]单元(实际可以少开辟1个)，将这n个数据记录存和L．r[2n一1]～L．r[2n一1]，且这4个有序表之问储于开始的连续／1,个存储单元中，4路插入排序在也依关键字值有序。设这4个有序表的开始位置和这2n个存储单元中进行。结束位置分别为firstl、first2、secondl、second2、thirdl、在数据记录随机的情况下，该算法关键字的平third2、fourthl、fourth2，置初始值分别为firstl=first2均比较次数和数据记录的平均移动记录次数都比传=0、secondl=second2=n、thir

6、dl=third2=n+1、统循环2路插入排序算法的有所减少，因此，在空问fourthl=fourth2=2n一1；设第1部分有序表和第2复杂度相同的情况下，其平均时间效率得到了进一部分有序表的关键字值的中间值为midkeyl=(L一步的提高。>r[0]．key+L一>r[n]．key)／2，第2部分有序表和第3部分有序表的关键字值的中间值为midkey2=(L一>r[n]．key+L一>r[n+1]．key)／2，第3部分收稿日期：2013—04—02有序表和第4部分有序表的关键字值的中间值为基金项目：甘肃省教育厅科研项目(1108B一01)midkey3=(L一>r[n+1]．k

7、ey+L一>r[2n一1]．作者简介：王昱(1965)，硕士，副教授，主要从事数据结构与算法设计的教学与研究。key)／2。2013年第6期工业仪表与自动化装置·77·其次，置i=4√=n一1，当i时，根据L．r[i]．后向前插入)，插入后使third2加1、i加1；如果L_rkey与midkeyl、midkey2、midkey3的比较结果，将[i]的关键字值大于等于midkey3，则将L．r[i]插入L．r[i]插入到4个有序表之一中：如果L．r[i]的