希尔排序增量序列讨论

1、希尔排序增量序列讨论高晓明(温州大学 物理与电子信息工程学院08信管本)摘要本文在希尔排序算法机制的基础上，通过不同增量序列对一些规模较大的待排序序列进行实验，并对不同输入数据在不同的增量序列下的希尔排序执行时间进行比较，探索增量序列对希尔排序的影响。关键字 希尔排序；增量序列；执行时间；The Discussion of Increment Series onShellsMethodGAO Xiaoming(College of Physics and Electro nic In formati on Engin eeri ng, WenZhou Un iversity, Admi nis

2、tratio n and in formatio n tech no logy)Abstract: This essay tests on some un sorted large arrays by referri ng to differe nt in creme nt a series, which is based on the Shells Method mecha ni sm. Furthermore, this series gives a compare of differe nt in put data s executinightime Method un der diff

3、ere nt in creme nt series, whichis aimed at explori ng how in creme nt series in flue nee Shells Method.Key words: Shells Method; in creme nt series; execut ing time一、引言希尔排序，又称为“缩小增量排序法”，是一种基于直接插入思想的排序方法。但希尔排序的时间耗费是所取增量序列的函数，到目前为止，尚未有人求得一种最好的增量序列。 所以一直以来希尔排序的分析都被认为是一个复杂的问题。本文在理论研究的基础上，通过大量数据的程序测试， 探

4、索如何选取恰当的增量序列，使得排序过程中所需的比较和移动次数相对较少，并且无论待排序列记录数有多少，程序的执行时间都能趋于最佳。二、希尔排序的基本思想直接插入排序法，在待排序的关键字序列基本有序且关键字个数n较小时，其算法的性能最佳。希尔排序利用直接插入排序的最佳性质，将待排序的关键字序列分成若干个较小的子序列，对子序列进行直接插入排序，使整个待排序序列排好序。在时间耗费上，较直接插入排序的性能有较大的改进。在进行直接插入排序时，若待排序记录序列已经有序时， 直接插入排序的时间复杂度可以提高到0 (n)。若待排序记录序列基本有序时，即序列中具有下列特性的记录较少时：ri.keyMaxrj.ke

5、y,(1 j v i),直接插入排序的效率会大大提高。先将待排序记录序列r1,r2,r3, , rj , , ,rn,以一定增量间隔h分割成若干个“较稀疏”子序列 r1,rh,r2h, , , r2,rh+1,r2h+1, ,r3,rh+2,r2h+2, , rh-1,r2h-1,r3h-1, , ,rn，对每个子序列分别进行直接插入排序，然后逐步减小步长h,对每个不同步长 h下的子序列进行相同的操作，直到步长为1时，再对整个记录进行一次直接插入排序。 首先选定记录间的距离，即步长为hi (i=1 )，在整个待排序记录序列中将所有间隔为h1的记录分成一组，进行内直接插入排序； 然后取i=i+1

6、，记录间的距离为 hi (hi v hi-1 ),在整个待排序记录序列中，将所有间 隔为d2的记录分为一组，进行组内直接插入排序；重复步骤多次， 直至记录间的距离 hi=1,此时整个只有一个子序列， 对该序列进行直 接插入排序，完成排序过程。如图所示，给出一个希尔排序过程的实例。初触键字序热取0 冷为4个刚(为4的？ 序虬各碑列内进克緘为：取人列*分为1个间隔为啲子05131742465570这样不管记录序列多么庞大,关键字多么复杂，在先前较大的分组步长 h下每个子序列的规模都不大，用直接插入排序效率都较高，尽管在随后的步长h递减分组中子序列越来越大，由于整个序列的有序性越来越明显，则排序效率

7、依然较高，这种改进是希尔排序的执行效率大大提高。三、测希尔排序平均执行时间的算法思想对于一个随机序列进行希尔排序，测试其平均执行时间。首先调用rand ()函数产生随机数，存放于一数组，再用希尔排序进行排序，用GetTickCou nt()分别记录排序前后时间，之差就是该排序所执行的时间。rand ()函数没有输入参数，可直接通过表达式rand ()来引用生成一个随机数，但由于rand ()函数是按指定的顺序来产生整数，因此每次执行上面的语句结果都是相同的 值，所以为了使程序在每次执行时都能生成一个新序列的随机值，通过为随机数生成器提供一粒新的随机种子。函数srand ()可以为随机数生成器播

8、散种子。只要种子不同rand ()函数就会产生不同的随机数序列。所以其算法描述为：sran d(u nsig ned)time(NULL); /*用系统时间当种子，对随机函数进行初始化*/for(i= 1;i=IOO;i+)k=rand()%50000; /*产生各个随机数*/start_time=GetTickCou nt;/*希尔排序前的时间 */ShellSort;en d_time=GetTickCou nt;/*希尔排序后的时间 */从而得出希尔排序执行过程所需要的时间为希尔排序前后的时间差(end_time-start_time);四、希尔增量研究1) 由于希尔排序的核心是以某个增

9、量h为间隔分组进行直接插入排序，如何选取增量 之间的间隔d，提高希尔排序程序执行效率，自然成为我们要研究的关键。2) 待排序列的记录个数N,这也是一个不容忽视的影响希尔排序程序执行效率的因素。3) 在希尔排序过程中，各趟的步长不同，使得第k遍排序后，第k+1遍排序时可能会 遇到多个逆序存在，影响排序的稳定性，从而影响排序执行效率。五、编程试验与结果分析选取以下四组增量排序序列ht1=N/2,N/4,N/8, ,1 ；kht2=2-1, , ,7,3,1 ；kht3=(3 -1)/2, ,13,4,1；ht4=N/3+1,N/9+1,N/27+1, ,1 ;编写希尔排序程序，用随机生成函数产生三

10、组数量较大的整数作为待排序列的关键字，分别用上述四种增量序列对各组待排序列进行排序，记录每个排序过程的比较次数、移动次数以及执行时间。1、保持待排序列的记录个数不变当元素N=100000,用随机生成数产生三组随机数，分别用以上四种增量序列对其进行希尔排序实验。记录每个排序过程的比较次数、移动次数和执行时间。测试结果如下表:增量组号比较次数移动次数执行时间(ms)ht1150967954257586632535683045232917834953899411109662ht2145699563914683622469714740461907834826200417720678ht31469079

11、84375752632442996441145256234505607418932062ht4139179573578357472398585536449624733880398354024762从实验测试的结果看，对于相同个数的三组随机生成整数记录在四种增量序列下程序排 序过程中的比较次数、移动次数以及执行时间等差别并不是很大，我们可以认为对于待排序序列的记录数相同下，各种基于上述四种增量序列，希尔排序算法的时间复杂度没有明显的 差异。2、待排序列的记录个数增加元素个数 N的值从小到大变化(N=10000,100000,1000000,10000000 )时，分别取增量 序列 hti=N/2

12、,N/4,N/8, , ,1 ； ht2=2k-1, , ,7,3,1 ； ht3=(3k-1)/2, , ,13,4,1 ； ht4=N/3+1,N/9+1,N/27+1, , ,1 ;以同样的程序进行实验， 得到不同N值，不同的增量序列下， 希尔排序程序的执行时间如下表：兀素个数增量比较次数移动次数执行时间(mSN=10000ht133368226166615ht230664925318416ht32797462539540ht42652272679580N=100000ht15096795425758663ht24697147404619062ht34429964411452563ht4

13、3917957357835747N=1000000ht175941566653121291154ht269536625614358511061ht36795265163812420999ht46515905860976081936N=10000000ht11145131840101503749118081ht21816965129172326338834991ht3103048392397717460016162ht491430979085430814613681根据上表的结果可以看出，当增量序列为ht4时，希尔排序的效率最优，增量序列ht3次之，ht2也好于hti说明奇数序列效率比偶数效率高

14、。而且随着元素个数N的增大，该特征更明显。六、结束语本文通过大量数据对希尔排序的增量序列进行初步的研究，得出结论：选取增量序列ht4=N/3+1,N/9+1,N/27+1, ,1进行希尔排序效率最高，而且性能稳定。参考文献1耿国华，数据结构一一C语言描述，北京，高等教育出版社，2005.72李井润.一种基于统计的分段排序算法J.微计算机应用，2004, 25(3) : 274 279附源代码：#in clude#in clude#in clude#defi ne N 100000void Shelll nsert(i nt *r,int n,i nt m,i nt &com,i nt & ex

15、c)/n为数组大小,int i,j;for( i=m+1;i=n ;i+)if(ri 0&r0rj;j-=m)com+;rj+m=rj;exc+;com+;rj+m=r0;exc+;com+;m为间隔;void ShellSort1(int *r,int n)/h u 增量序列排序 long start_time,e nd_time;start_time =(lo ng)GetTickCo un t();int com=0,exc=0,m=1;dom=2*m;ShellI nsert(r, n,N/m,com,exc);/1 5 9 13 17while(mN);end_time =(long

16、)GetTickCount(); 结束时间 prin tf( printf(比较次数 printf(移动次数 printf(执行时间*希尔排序：*n);%ldn,com);%ldn ,exc);%dn,e nd_time-start_time);void ShellSort2(int *r,int n)/h t2 增量序列排序long start_time,e nd_time; start_time =(lo ng)GetTickCo un t(); int com=0,exc=0,m=1,k=1;dom=2*m+1;k+;while(m=N);doint p=1;for(i nt i=0;i

17、=1);end_time =(long)GetTickCount(); 结束时间prin tf(* printf(比较次数 printf(移动次数 printf(执行时间希尔排序：*n);%ldn,com);%ldn ,exc);%dn,e nd_time-start_time);void ShellSort3(int *r,int n)/h t3 增量序列排序 long start_time,e nd_time;start_time =(lo ng)GetTickCo un t();int com=0,exc=0,m=1,k=1;dom=3*m+2;k+; while(m=N/2); doi

18、nt p=1;for(i nt i=0;i=1);end_time =(long)GetTickCount(); 结束时间prin tf(*printf(比较次数：希尔排序： *n);%ldn,com);printf(” 移动次数：ldn,exc);printf(” 执行时间：%dn,end_time-start_time); void ShellSort4(int *r,int n)/h t4 增量序列排序 long start_time,e nd_time;start_time =(lo ng)GetTickCo un t();int com=0,exc=0,m=1;dom=3*m;ShellI nsert(r, n,N/m+1,com,exc);while(N/m1);希尔排序：*门);%ldn,com);%ldn ,exc);%dn,e nd_time-start_time);*end_time =(long)GetTickCount(); 结束时间 prin tf( printf(比较次数 printf(移动次数 printf(执行时间void Sort(i nt *r