《希尔排序增量序列讨论.doc》由会员分享，可在线阅读，更多相关《希尔排序增量序列讨论.doc（9页珍藏版）》请在金锄头文库上搜索。
1、希尔排序增量序列讨论高晓明(温州大学 物理与电子信息工程学院 08信管本)摘要 本文在希尔排序算法机制的基础上，通过不同增量序列对一些规模较大的待排序序列进行实验，并对不同输入数据在不同的增量序列下的希尔排序执行时间进行比较，探索增量序列对希尔排序的影响。关键字 希尔排序；增量序列；执行时间；The Discussion of Increment Series on Shells MethodGAO Xiaoming(College of Physics and Electronic Information Engineering, Wen Zhou University, Administr
2、ation and information technology)Abstract：This essay tests on some unsorted large arrays by referring to different increment a series, which is based on the Shells Method mechanism. Furthermore, this series gives a compare of different input datas executing time of Shells Method under different incr
3、ement series, which is aimed at exploring how increment series influence Shells Method.Key words: Shells Method; increment series; executing time一、引言希尔排序，又称为“缩小增量排序法”，是一种基于直接插入思想的排序方法。但希尔排序的时间耗费是所取增量序列的函数，到目前为止，尚未有人求得一种最好的增量序列。所以一直以来希尔排序的分析都被认为是一个复杂的问题。本文在理论研究的基础上，通过大量数据的程序测试，探索如何选取恰当的增量序列，使得排序过程中所需
4、的比较和移动次数相对较少，并且无论待排序列记录数有多少，程序的执行时间都能趋于最佳。二、希尔排序的基本思想直接插入排序法，在待排序的关键字序列基本有序且关键字个数n较小时，其算法的性能最佳。希尔排序利用直接插入排序的最佳性质，将待排序的关键字序列分成若干个较小的子序列，对子序列进行直接插入排序，使整个待排序序列排好序。在时间耗费上，较直接插入排序的性能有较大的改进。在进行直接插入排序时，若待排序记录序列已经有序时，直接插入排序的时间复杂度可以提高到O（n）。若待排序记录序列基本有序时，即序列中具有下列特性的记录较少时：ri.keyMaxrj.key,(1ji),直接插入排序的效率会大大提高。先
5、将待排序记录序列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，记录间的距离为hi（hihi-1），在整个待排序记录序列中，将所有间隔为d2的记录分为一组，进行组内直接
6、插入排序；重复步骤多次，直至记录间的距离hi=1，此时整个只有一个子序列，对该序列进行直接插入排序，完成排序过程。如图所示，给出一个希尔排序过程的实例。这样不管记录序列多么庞大，关键字多么复杂，在先前较大的分组步长h下每个子序列的规模都不大，用直接插入排序效率都较高，尽管在随后的步长h递减分组中子序列越来越大，由于整个序列的有序性越来越明显，则排序效率依然较高，这种改进是希尔排序的执行效率大大提高。三、 测希尔排序平均执行时间的算法思想对于一个随机序列进行希尔排序，测试其平均执行时间。首先调用rand（）函数产生随机数，存放于一数组，再用希尔排序进行排序，用GetTickCount()分别记录
7、排序前后时间，之差就是该排序所执行的时间。rand（）函数没有输入参数，可直接通过表达式rand（）来引用生成一个随机数，但由于rand（）函数是按指定的顺序来产生整数，因此每次执行上面的语句结果都是相同的值，所以为了使程序在每次执行时都能生成一个新序列的随机值，通过为随机数生成器提供一粒新的随机种子。函数srand（）可以为随机数生成器播散种子。只要种子不同rand（）函数就会产生不同的随机数序列。所以其算法描述为：srand(unsigned)time(NULL); /*用系统时间当种子，对随机函数进行初始化*/for(i= 1;i=l00;i+)k=rand()%50000; /*产生各
8、个随机数*/start_time=GetTickCount;/*希尔排序前的时间*/ShellSort;end_time=GetTickCount;/*希尔排序后的时间*/从而得出希尔排序执行过程所需要的时间为希尔排序前后的时间差（end_time-start_time）;四、 希尔增量研究1） 由于希尔排序的核心是以某个增量h为间隔分组进行直接插入排序，如何选取增量之间的间隔d，提高希尔排序程序执行效率，自然成为我们要研究的关键。2）待排序列的记录个数N，这也是一个不容忽视的影响希尔排序程序执行效率的因素。3）在希尔排序过程中，各趟的步长不同，使得第k遍排序后，第k+1遍排序时可能会遇到多个
9、逆序存在，影响排序的稳定性，从而影响排序执行效率。五、编程试验与结果分析选取以下四组增量排序序列ht1=N/2,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；编写希尔排序程序，用随机生成函数产生三组数量较大的整数作为待排序列的关键字，分别用上述四种增量序列对各组待排序列进行排序，记录每个排序过程的比较次数、移动次数以及执行时间。1、保持待排序列的记录个数不变当元素N=100000，用随机生成数产生三组随机数，分别用以上四种增量序列对其进行希尔排序实验。记录每个排序过程的比较次数、移动次数和执行时间。测
10、试结果如下表：增量组号比较次数移动次数执行时间（ms）ht1150967954257586632535683045232917834953899411109662ht2145699563914683622469714740461907834826200417720678ht3146907984375752632442996441145256234505607418932062ht4139179573578357472398585536449624733880398354024762 从实验测试的结果看，对于相同个数的三组随机生成整数记录在四种增量序列下程序排序过程中的比较次数、移动次数以及执行
11、时间等差别并不是很大，我们可以认为对于待排序序列的记录数相同下，各种基于上述四种增量序列，希尔排序算法的时间复杂度没有明显的差异。2、待排序列的记录个数增加元素个数N的值从小到大变化（N=10000,100000,1000000,10000000）时，分别取增量序列ht1=N/2,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值，不同的增量序列下，希尔排序程序的执行时间如下表：元素个数增量比较次数移动次数执行时间（ms）N=10000ht133368226166615h
12、t230664925318416ht32797462539540ht42652272679580N=100000ht15096795425758663ht24697147404619062ht34429964411452563ht43917957357835747N=1000000ht175941566653121291154ht269536625614358511061ht36795265163812420999ht46515905860976081936N=10000000ht11145131840101503749118081ht21816965129172326338834991ht3
13、103048392397717460016162ht491430979085430814613681根据上表的结果可以看出，当增量序列为ht4时，希尔排序的效率最优，增量序列ht3次之，ht2也好于ht1说明奇数序列效率比偶数效率高。而且随着元素个数N的增大，该特征更明显。六、 结束语 本文通过大量数据对希尔排序的增量序列进行初步的研究，得出结论：选取增量序列ht4=N/3+1,N/9+1,N/27+1,1进行希尔排序效率最高，而且性能稳定。参考文献1耿国华，数据结构C语言描述,北京，高等教育出版社，2005.72李井润一种基于统计的分段排序算法J微计算机应用，2004，25(3)：27427
14、9附源代码：#include#include#include#define N 100000void ShellInsert(int *r,int n,int m,int &com,int &exc)/n为数组大小，m为间隔；int i,j;for( i=m+1;i=n;i+) if(ri0&r0rj;j-=m) com+; rj+m=rj;exc+; com+; rj+m=r0;exc+; com+; void ShellSort1(int *r,int n)/ht1增量序列排序long start_time,end_time; start_time =(long)GetTickCount(); int com=0,exc=0,m=1; dom=2*m;ShellIn
