首页 [笔记]希尔排序增量序列讨论

[笔记]希尔排序增量序列讨论

[笔记]希尔排序增量序列讨论[笔记]希尔排序增量序列讨论希尔排序增量序列讨论高晓明 (温州大学物理与电子信息工程学院 08信管本) 摘要本文在希尔排序算法机制的基础上，通过不同增量序列对一些规模较大的待排序序列进行实验，并对不同输入数据在不同的增量序列下的希尔排序执行时间进行比较，探索增量序列对希尔排序的影响。关键字希尔排序;增量序列;执行时间; The Discussion of Increment Series on Shell’s Method GAO Xiaoming (College of Physic...

[笔记]希尔排序增量序列讨论希尔排序增量序列讨论高晓明 (温州大学物理与电子信息工程学院 08信管本) 摘要本文在希尔排序算法机制的基础上，通过不同增量序列对一些规模较大的待排序序列进行实验，并对不同输入数据在不同的增量序列下的希尔排序执行时间进行比较，探索增量序列对希尔排序的影响。关键字希尔排序;增量序列;执行时间; The Discussion of Increment Series on Shell’s Method GAO Xiaoming (College of Physics and Electronic Information Engineering, Wen Zhou University, Administration and information technology) Abstract:This essay tests on some unsorted large arrays by referring to different increment a series, which is based on the Shell's Method mechanism. Furthermore, this series gives a compare of different input data’s executing time of Shell's Method under different increment series, which is aimed at exploring how increment series influence Shell's Method. Key words: Shell's Method; increment series; executing time 一、引言希尔排序，又称为“缩小增量排序法”，是一种基于直接插入思想的排序方法。但希尔排序的时间耗费是所取增量序列的函数，到目前为止，尚未有人求得一种最好的增量序列。所以一直以来希尔排序的分析都被认为是一个复杂的问题。本文在理论研究的基础上，通过大量数据的程序测试，探索如何选取恰当的增量序列，使得排序过程中所需的比较和移动次数相对较少，并且无论待排序列记录数有多少，程序的执行时间都能趋于最佳。二、希尔排序的基本思想直接插入排序法，在待排序的关键字序列基本有序且关键字个数n较小时，其算法的性能最佳。希尔排序利用直接插入排序的最佳性质，?将待排序的关键字序列分成若干个较小的子序列，对子序列进行直接插入排序，使整个待排序序列排好序。在时间耗费上，较直接插入排序的性能有较大的改进。?在进行直接插入排序时，若待排序记录序列已经有序时，直接插入排序的时间复杂度可以提高到O(n)。若待排序记录序列基本有序时，即序列中具有下列特性的记录较少时:r[i].key 表达式rand()来引用生成一个随机数，但由于rand()函数是按指定的顺序来产生整数，因此每次执行上面的语句结果都是相同的值，所以为了使程序在每次执行时都能生成一个新序列的随机值，通过为随机数生成器提供一粒新的随机种子。函数srand()可以为随机数生成器播散种子。只要种子不同rand()函数就会产生不同的随机数序列。所以其算法描述为: srand((unsigned)time(NULL)); /*用系统时间当种子，对随机函数进行初始化*/ for(i= 1;i<=l00;i++) k=rand()%50000; /*产生各个随机数*/ start_time=GetTickCount;/*希尔排序前的时间*/ ShellSort; end_time=GetTickCount;/*希尔排序后的时间*/ 从而得出希尔排序执行过程所需要的时间为希尔排序前后的时间差 (end_time-start_time); 四、希尔增量研究 1)由于希尔排序的核心是以某个增量h为间隔分组进行直接插入排序，如何选取增量之间的间隔d，提高希尔排序程序执行效率，自然成为我们要研究的关键。 2)待排序列的记录个数N，这也是一个不容忽视的影响希尔排序程序执行效率的因素。 3)在希尔排序过程中，各趟的步长不同，使得第k遍排序后，第k+1遍排序时可能会遇到多个逆序存在，影响排序的稳定性，从而影响排序执行效率。五、编程试验与结果分析选取以下四组增量排序序列 h=N/2,N/4,N/8,„,1;t1 kh=2-1,„,7,3,1; t2 kh=(3-1)/2,„,13,4,1; t3 h=N/3+1,N/9+1,N/27+1,„,1; t4 编写希尔排序程序，用随机生成函数产生三组数量较大的整数作为待排序列的关键字，分别用上述四种增量序列对各组待排序列进行排序，记录每个排序过程的比较次数、移动次数以及执行时间。 1、保持待排序列的记录个数不变当元素N=100000，用随机生成数产生三组随机数，分别用以上四种增量序列对其进行希尔排序实验。记录每个排序过程的比较次数、移动次数和执行时间。测试结果如下表: 增量组号比较次数移动次数执行时间(ms) 1 5096795 4257586 63 h t12 5356830 4523291 78 3 4953899 4111096 62 1 4569956 3914683 62 h 2 4697147 4046190 78 t2 3 4826200 4177206 78 1 4690798 4375752 63 h 2 4429964 4114525 62 t3 3 4505607 4189320 62 1 3917957 3578357 47 h t42 3985855 3644962 47 3 3880398 3540247 62 从实验测试的结果看，对于相同个数的三组随机生成整数记录在四种增量序列下程序排序过程中的比较次数、移动次数以及执行时间等差别并不是很大，我们可以认为对于待排序序列的记录数相同下，各种基于上述四种增量序列，希尔排序算法的时间复杂度没有明显的差异。 2、待排序列的记录个数增加元素个数N的值从小到大变化(N=10000,100000,1000000,10000000)时，分别取增 kk量序列h=N/2,N/4,N/8,„,1;h=2-1,„,7,3,1;h=(3-1)/2,„,13,4,1;t1t2t3 h=N/3+1,N/9+1,N/27+1,„,1;以同样的程序进行实验，得到不同N值，不同的增量序列下，t4 希尔排序程序的执行时间如下表: 元素个数增量比较次数移动次数执行时间(ms) h 333682 261666 15 t1 N=10000 h 306649 253184 16 t2 h 279746 253954 0 t3 h 265227 267958 0 t4 h 5096795 4257586 63 t1 N=100000 h 4697147 4046190 62 t2 h 4429964 4114525 63 t3 h 3917957 3578357 47 t4 h 75941566 65312129 1154 t1 N=1000000 h 69536625 61435851 1061 t2 h 67952651 63812420 999 t3 h 65159058 60976081 936 t4 h 1145131840 1015037491 18081 t1 N=10000000 h 1816965129 1723263388 34991 t2 h 1030483923 977174600 16162 t3 h 914309790 854308146 13681 t4 根据上表的结果可以看出，当增量序列为h时，希尔排序的效率最优，增量序列ht4t3次之，h也好于h说明奇数序列效率比偶数效率高。而且随着元素个数N的增大，该特征t2t1 更明显。六、结束语本文通过大量数据对希尔排序的增量序列进行初步的研究，得出结论:选取增量序列h=N/3+1,N/9+1,N/27+1,„,1进行希尔排序效率最高，而且性能稳定。t4 参考文献 [1]耿国华，《数据结构——C语言描述》,北京，高等教育出版社，2005.7 [2]李井润(一种基于统计的分段排序算法[J](微计算机应用，2004，25(3):274—279 附源代码: #include #include #include #define N 100000 void ShellInsert(int *r,int n,int m,int &com,int &exc)//n为数组大小，m为间隔; { int i,j; for( i=m+1;i<=n;i++) { if(r[i]0&&r[0]=1); end_time =(long)GetTickCount();//结束时间 printf("***********希尔排序:***********\n"); printf("比较次数:%ld\n",com); printf("移动次数:%ld\n",exc); printf("执行时间:%d\n",end_time-start_time); } void ShellSort3(int *r,int n)//h增量序列排序 t3 { long start_time,end_time; start_time =(long)GetTickCount(); int com=0,exc=0,m=1,k=1; do{ m=3*m+2; k++; }while(m<=N/2); do{ int p=1; for(int i=0;i=1); end_time =(long)GetTickCount();//结束时间 printf("***********希尔排序:***********\n"); printf("比较次数:%ld\n",com); printf("移动次数:%ld\n",exc); printf("执行时间:%d\n",end_time-start_time); } void ShellSort4(int *r,int n)//h增量序列排序 t4 { long start_time,end_time; start_time =(long)GetTickCount(); int com=0,exc=0,m=1; do{ m=3*m; ShellInsert(r,n,N/m+1,com,exc); }while(N/m>1); end_time =(long)GetTickCount();//结束时间 printf("***********希尔排序:***********\n"); printf("比较次数:%ld\n",com); printf("移动次数:%ld\n",exc); printf("执行时间:%d\n",end_time-start_time); } void Sort(int *r,int n) { int i=1; int *d=(int*)malloc((n+1)*sizeof(int)); for(i=1;i<=n;i++) d[i]=r[i]; ShellSort1(d,n); int *e=(int*)malloc((n+1)*sizeof(int)); for(i=1;i<=n;i++) e[i]=r[i]; ShellSort2(e,n); int *f=(int*)malloc((n+1)*sizeof(int)); for(i=1;i<=n;i++) f[i]=r[i]; ShellSort3(f,n); int *g=(int*)malloc((n+1)*sizeof(int)); for(i=1;i<=n;i++) g[i]=r[i]; ShellSort4(g,n); } void s_rand(int *&a,int n) { for(int i=1;i<=n;i++) a[i]=rand()%50000; } int main() { int *a1,*a2,*a3; a1=(int*)malloc((N+1)*sizeof(int)); a2=(int*)malloc((N+1)*sizeof(int)); a3=(int*)malloc((N+1)*sizeof(int)); s_rand(a1,N); s_rand(a2,N); s_rand(a3,N); Sort(a1,N); Sort(a2,N); Sort(a3,N); return 0;

                    本文档为【[笔记]希尔排序增量序列讨论】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

[笔记]希尔排序增量序列讨论

你可能还喜欢