一种改进的循环2路插入排序算法.pdf

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

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

2、anwen，LIDelu(SchoolofPhysicsandInformationScie~e，TianshuiNormalUniversity，GansuTiamhui741000，China)Abstract：Inthispaper，animproved2一waycircularinsertionsortalgorithmisproposed，anditsalgorithmprincipleandimplementationareintroduced．Thetimeeficiencyofthis2一wayinsertionsortalgorithmisbetterthanori

3、ginalones，andthespacecomplexityisreducedto0(1)fromtheoriginal0(n)．Keywords：datastructure；2一wayinsertionsort；algorithm得到了改善，而且使得算法的空间复杂度由原来的0引言0(凡)降为0(1)。直接插入排序算法是一种最简单的排序算法，它1算法思想的时间复杂度为D()⋯，空间复杂度为D(1)，在数据量较小的情况下，使用较为普遍。随着数据量的增设待排序数据存放在顺序表L．r[0]一Lr[n一加，则不宜采用直接插入排序算法，可选用折半插入1]中，另设一个存放数据记录的临时存储单元

4、。排序算法，尽管折半插入排序算法的时间复杂度和空在实现算法时，将顺序表L．r看作一个循环向量。间复杂度与直接插入排序算法相同，但它减少了关键初始时，对L．r[0]和L_r[n一1]的关键字进行比字之间的比较次数，提高了排序的时间效率。较，将关键字较小者存放在L．r[n一1]中，关键字较传统2路插入排序算法是对直接插入排序算大者存放在L．r[0]中，这样有序区为L．r[一1]～法和折半插入排序算法的一种改进，算法的时间复杂L．r[0]。置i=1，=n一2，mid=一1(或mid=度是O(／／,)，由于额外增加了n个记录的辅助空间，0)，从P=i开始，到p结束，将L．rEp]插入到前使得

5、算法的空间复杂度变为0(n)。在理想情况下，面的有序区中。每次插入时，首先将Lr[P]暂存到传统2路插入排序算法的平均比较次数和平均移动临时存储单元中，然后让L．rEp]与L．r[mid]进行记录次数是直接插入排序算法的一半，在最坏情况下比较，如果L．r[P]的关键字小于L．r[mid]的关键(即数据的关键字是逆序)，它的比较次数和移动记字，就将L．rEp]插入到L．rEj+1]一L．r[mid]中：先录次数则退化到和直接插入排序算法相同。将L．rEj]存放到L．rEp]中以腾出插入空间，之后一该文给出了一种对传统2路插入排序算法的改边查找插入位置一边移动数据记录，找到插入位置进算法

6、，不论数据的分布如何，它的比较次数和移动后，将临时存储单元中暂存的数据记录存入插入记录次数都减少为直接插入排序算法的一半，虽然位置，再使减1；如果L．r[P]的关键字大于等于算法的时间复杂度仍然是0(n)，但总的排序效率L．r[mid]的关键字，就将L．rEp]插入到Lr[mid]～L．r[i一1]中：一边查找插入位置一边移动数据记录，找到插人位置后，将临时存储单元中暂存的数收稿日期：2011—08—22据记录存入插入位置，再使i加1，P=i。每次插入基金项目：甘肃省教育厅科研项目(1108B—O1)作者简介：王昱(1965)，硕士，副教授，主要从事数据结构与算后，重新计算有序区的中

7、间位置mid：(++)／法设计的教学与研究工作。2，如果mid≥n，则mid=mid．n。当所有数据记录插·80·工业仪表与自动化装置2011年第6期入结束后，i与相邻，位置i的数据记录为关键字最for(P=i；p<=j；){小者，位置的数据记录为关键字最大者，如果i不x=L一>r[P]；／／待插入元素暂存入临时等于0(或不等于一1)，将L．r进行一次转储，则存储单元L．r中即为排好序的数据。if(x．keyr[mid]．key){／／需插入关于L