二分双插入排序算法及其性能研究.doc

二分双插入排序算法及其性能研究第16卷第2期(2ol1)甘音高.斥拒vo1.16no.2(2011)二分双插入排序算法及其性能研究祁建宏任志国达文姣岳秋菊(兰州城市学院信息工程学院,甘肃兰州730070)摘要:在分析了传统二分插入排序算.法i能的基础上,给出了一种二分双插入排序算法,这种排序算法使时间性能得到了极大改善.关键词:算法;二分插入排序;时间复杂度;空间复杂度中图分类号:tp311.12文献标识码:a文章编号:10089020(2011)02026031.问题的提出传统二分插入排序算法的基本思想是:设待排序记录存放在数组r的r【1到rr?length,开始时认为由1卜条记录所组成的序列是有序的,然后从r中的第2条记录开始依次插入到前面的有序子序列中去,重复此操作,直到所有的待排序记录都被插人为止.设待排序记录为:47,30,73,89,78,11,20,9,以升序(非递减)为例,则其排序过程如下图所示:初始关键字:473073897811209i=l(47)i=2(3047)?i=3(304773)i=4(30477389)i=5(3047737889)i=6(113047737889)i=3(11203047737889)i=7(911203047737889)在确定待插入记录在有序子序列中的位置时,可采用顺序查找,也可采用二分查找.当然,采用二分查找法的速度更快.以下是采用二分查找法时的二分插入排序算法./类型定义:#definemaxsize6000typedefstructfintkey;/定记录的关键字为整型jrectype;typedefstructrectypermaxsize+1;/:放记录的数组,其中0号用于交换intlength;/性表长度,即实际记录个数sqlist;/采用二分查找的插入排序算法voidbinserts0rt(sqlist1)finti,j,high,low,m;f0r(i=2;i<=l一>length;i+)f1->ro=l一>r【当前待插入记录存人r【0low=1;/以下采用二分查找法确定待插入记录位置high=i-l;while(1ow<=high)m=(1ow+high)/2;if(1->ro.key<l->rm.key)high=m一1:elselow=m+l;jforo=i一1;j>=high+1;j一),/将比待插入记录大的记录后移1->rj+1】=l一>r【j】;1->rhigh+1=l一>r0;,/插入记录二分插入排序算法简单高效,相对于直接插入排序而言,比较次数要少一些,但移动记录的次数跟直接插入排序相同.2.二分双插入排序.为进一步减少比较及移动次数,可考虑一次以两条记录为单位进行插入.仍以非递减为例,每次插收稿日期:20100923作者简介:祁建宏(1972一),男,甘肃临洮人,讲师.研究方向:程序设计与算法的教学26第l6卷第2期(2011)祁建宏等:二分双插入排序算法及其性能研究入时先找出待插人两条记录中的较大者,按二分查找法确定较大记录的位置,在向后移动已有序记录时一次移动两条记录(因为较小记录肯定将来放在较大记录之前);插入较大记录后再按传统二分插入排序算法在较大记录所处位置与第一条记录所处位置之间插人较小记录.因为在插入较大记录时已经缩小了较小记录的查找范围,同时,在给较大记录移出存放空间时已经提前将一部分本来应该在插入较小记录时才移动的记录提前一趟进行了移动,从而既减少了确定较小记录位置时的比较次数,又减少了移动次数,性能得到了改善.假定r1】到ri一1间的记录已经是有序的,现要将从rin最后的所有记录再插入到有序序列中去,可按以下步骤进行:1.将ri和ri+l】中较大记录放人max,较小记录放人min;2.用二分查找法确定max在r1nri一11这一段中应该所处的位置,用high1表示;3.将从rhighl+1jril】这段中的记录向后移动两条记录的位置;4.将max放人rhighl+21l;5.用二分查找法确定min在r1到rhigh1这一段中应该所处的位置,用high2表示;6.将从rhigh2+1!jrhigh1这段中的记录向后移动一条记录的位置;7.将min放人rhigh2+l1;8.重复1至7,直到所有记录插入完为至./-分双插入排序算法voidbbinserts0rt(sqlist1)inti,j,highl,lowl,high2,low2,in,b;rectypemax,min;/确定插入的起始位置,偶数个则从第一个开始插入,奇数个则从第二个开始插人ifo->length%2=o)b=l;b=2:foro=b;i+l<=l一>length;i+=2,iif(1一>ri.key<=l一>ri+1.key,i/将待插入两条记录按大小分别放人max,minmin=l-一>r【i;ma)【=l一>r【i+1】;elsemin=l->ri+1;max=l->ri;)lowl=l;highl=i一1;/用二分法确定较大数的位置while(1ow1<=high1)m=(10w1+high1)/2;if(max.key<l一>rim.key)highl=m-1;elselowl=m+l;jfor(j=i一1;j>=highl+l;j一)/后移记录,为待插入数提供位置,一次移两个l一>rj+2】=l一>rj;1->rhigh1+2=max;/人较大数low2=1;high2=high1;/用二分法确定较小数的插入位置,只在较大数位置及起始位置之间查询即可while(10w2<=high2)m:(1ow2+high2)/2;if(rain.key<l->rm.key)high2=m-1;elselow2=m+1;)for(j=highl;j>=high2+1;j一)/后移记录,为待插入数提供位置,一次移一个1->rj+1:l一>rj;l一>rhigh2+1=min;/插入较小数表1二分双插入排序传统二分插入排序性能对比记录二分双插入排序传统二分插入排序比例(双,传统)条数比较次数移动次数比较次数移动次数比较次数移动次数10oo8251650118586248ol69.6l%66.53%50oo527304l4421054508620185896.74%66.82%10000l15493166505101190272494954897.03%66,.74殇50()o0693268416330724711407624344l0897.a5%66.68%27第16卷第2期(2011)寸音高旰子拒从描述中可看出,这种方法在确定较大数的位置的同时,实际上也缩小了较小数的搜索范围并提前对部分记录进行了移动,从而减少了较小数的比较及移动次数.3.性能分析比较通过分析可知,传统二分插入排序的时间复杂度为o(n),空间方面需要一条记录的附加空间.二分双插入排序算法空间方面需要两条记录的附加空间,时间复杂度仍为o(n),跟传统的二分插入排序属于同一个数量级,但具体的比较及移动次数会减少.表1列出一组随机数对两种排序方法进行测试的结果(每一种情况都是10次测试的平均值).从测试结果可知,在记录数比较多时,比较次数的减少不明显,但移动次数有明显的减少,约减少了1/3,效果还是比较明显,可以有效提高排序效率,同时对于提高手工排序的效率也具有很大的借鉴意义.参考文献:【11严蔚敏,吴伟民.数据结构【m】.北京:清华大学出版社,1997.10.【2】耿国华.数据结构(c语言版)m】.西安:西安电子科技大学出版社,2002.【3】傅清祥,王晓东.算法与数据结构【m】.北京:电子工业出版社.1998.4】谭浩强.c程序设计【m】.北京:清华大学出版社,1996.【5】任志国,蔡小龙等.插入排序算法的双链表模拟j】.电脑编程技巧与维护,2010(06):89.astudyonthealgorithmofbinarydoubleinsertionsortanditsperformanceq1帆一hongrenzhi-guodawen-jiaoyueqiu-ju(schoolofinformationscienceandengineering,lanzhoucityuniversity,lanzhougansu730070)abstract:byanalyzingthealgorithmoftraditionalbinaryinsertionsort,the