一种非循环2路插入排序算法.pdf

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

1、·66·工业仪表与自动化装置2012年第2期一种非循环2路插入排序算法王昱，杨小萍，陈延文，李德录(天水师范学院物理与信息科学学院，甘肃天水741000)摘要：提出了一种非循环2路插入排序算法，给出了算法思想及其实现，该算法与传统2路插入排序算法相比，时间效率得到了改善，空间复杂度由原来的0(n)降低为0(1)。关键词：数据结构；2路插入排序；算法中图分类号：TP311文献标志码：A文章编号：1000—0682(2012)02—0066—03Anoncircular2-wayinsertionsortalgorithmWANGYu，YANG

2、Xiaoping，CHENYanwen，LIDelu(SchoolofPhysicsandInformationScience，TianshuiNormalUniversity，GansuTianshui741000，China)Abstract：Inthispaper，anoncircular2-wayinsertionsortalgorithmisproposed，anditsalgorithmprincipleandimplementationareintroduced．Thetimecomplexityofthis2-wayinse

3、rtionsortalgorithmisbetterthanoriginalones，andthespacecomplexityisreducedto0(1)fromtheoriginalO(n)．Keywords：datastructure；2-wayinsertionsort；algorithm0引言。在实现算法时，并不将其看作一个循环向量。初始时，对顺序表L．r的所有记录的关键字值进行比直接插入排序算法是一种最简单的排序算法，较，将关键字值最小的记录存放在Lr[0]中，关键它的时间复杂度为O(n)，空间复杂度为O(1)⋯。字值最大的记

4、录存放在L．r[n一1]中，这样就在顺传统2路插入排序算法是对直接插入排序算法和折序表L．r的前后两端形成了2个只含有一个记录的半插入排序算法的一种改进，额外开辟了n个记录有序表L．r[0]～L．r[0]和L．r[n一1]～L．r[n一的辅助空间(与待排序顺序表同类型的数组，并将1]，同时计算L．r[0]和L．r[n一1]的关键字值的中其看作一个循环向量)，算法的时间复杂度是问值midkey(即midkey：(L．r[0]．key+L．r[n一O(凡)，空间复杂度为O(n)。1]．key)／2)。然后，置i=1，=n一2，从P=i开始，该文

5、提出了一种非循环2路插人排序算法，即到P结束，根据L．r[P]．key与midkey的比较结将待排序顺序表并不看成循环向量，也不额外增加果，将L_r[P]插入到前端或后端的有序表中。每次凡个记录的辅助空问，只另设一个存放数据记录的插入时，首先将L．r[P]暂存到临时存储单元中，临时存储单元，在原顺序表上进行排序。在一般情然后让(即原来的L．r[P])的关键字值与midkey况下，其比较次数和移动记录次数都是直接插入排进行比较，如果的关键字值小于midkey，则将插序算法的一半，虽然算法的时间复杂度仍然是入到前端的有序表L．r[0]～L．r[

6、i一1]中，然后使iO(／Z)，但与传统2路插入排序算法相比，该算法的加1，P=i；如果的关键字值大于等于midkey，则先时间效率得到了改善，而且使得算法的空间复杂度将L．r[j]存放到L．rip](即L．r[i])中以腾出插入由原来的O(n)降为0(1)。位置，然后将插入到后端的有序表L．r[+1]～1算法思想L．r[n一1]中，最后使减1。每次插入记录时，既可以采用直接插入，也可以采用折半插入，如果采用折设待排序的一组记录存放在顺序表L．r[0]～半插入，则将更进一步提高算法的时间效率。L．r[n一1]中，另设一个存放记录的临时存储单

7、元2算法实现收稿日期：2012—01一O4该文采用c语言来描述算法，有关类型定义如下：基金项目：甘肃省教育厅科研项目(1108B一01)#defineMAXSIZE100／／用作示例的顺序表的作者简介：王昱(1965)，硕士，副教授，主要从事数据结构与算法设计的教学与研究。最大长度2012年第2期工业仪表与自动化装置·67·typedefintKeyType；／／关键字类型，定义为整elseif(i!=L一>length一1&&j==0){数类型t=L一>r[L一>length一1]；typedefstruct{L一>r[L一>length

8、一1]=L一>r[j]；KeyTypekey；／／关键字项L一>r[J]=t；／／InfoTypeotherinfo；／／其他数据项，不用t=L一>r[0]；}RedType；／