希尔排序增量序列讨论.doc

希尔排序增量序列讨论
高晓明
(温州大学 物理与电子信息工程学院 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<Max{r[j].key},(1≤j＜i),直接插入排序的效率会大大提高。
先将待排序记录序列{r[1],r[2],r[3]…，r[j]，…，r[n]},以一定增量间隔h分割成若干个“较稀疏”子序列{r[1],r[h],r[2h]，…}，{r[2],r[h+1],r[2h+1],…}，{r[3],r[h+2],r[2h+2],…}，{r[h-1],r[2h-1],r[3h-1]，…,r[n]}，对每个子序列分别进行直接插入排序，然后逐步减小步长h，对每个不同步长h下的子序列进行相同的操作，直到步长为1时，再对整个记录进行一次直接插入排序。
①首先选定记录间的距离，即步长为hi（i=1），在整个待排序记录序列中将所有间隔为h1的记录分成一组，进行内直接插入排序；
②然后取i=i+1，记录间的距离为hi（hi＜hi-1），在整个待排序记录序列中，将所有间隔为d2的记录分为一组，进行组内直接插入排序；
重复步骤②多次，直至记录间的距离hi=1，此时整个只有一个子序列，对该序列进行直接插入排序，完成排序过程。
如图所示，给出一个希尔排序过程的实例。

这样不管记录序列多么庞大，关键字多么复杂，在先前较大的分组步长h下每个子序列的规模都不大，用直接插入排序效率都较高，尽管在随后的步长h递减分组中子序列越来越大，由于整个序列的有序性越来越明显，则排序效率依然较高，这种改进是希尔排序的执行效率大大提高。
三、 测希尔排序平均执行时间的算法思想
对于一个随机序列进行希尔排序，测试其平均执行时间。首先调用rand（）函数产生随机数，存放于一数组，再用希尔排序进行排序，用GetTickCount()分别记录排序前后时间，之差就是该排序所执行的时间。
rand（）函数没有输入参数，可直接通过表达式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遍排序时可能会遇到多个逆序存在，影响排序的稳定性，从而影响排序执行效率。
五、编程试验与结果分析
选取以下四组增量排序序列
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，用随机生成数产生三组随机数，分别用以上四种增量序列对其进行希尔排序实验。记录每个排序过程的比较次数、移动次数和执行时间。测试结果如下表：
增量
组号
比较次数
移动次数
执行时间（ms）

ht1
1
5096795
4257586
63
2
5356830
4523291
78
3
4953899
4111096
62

ht2
1
4569956
3914683
62
2
4697147
4046190
78
3
4826200
4177206
78

ht3
1
4690798
4375752
63
2
4429964
4114525
62
3
4505607
4189320
62

ht4
1
3917957
3578357
47
2
3985855
3644962
47
3
3880398
3540247
62
从实验测试的结果看，对于相同个数的三组随机生成整数记录在四种增量序列下程序排序过程中的比较次数、移动次数以及执行时间等差别并不是很大，我们可以认为对于待排序序列的记录数相同下，各种基于上述四种增量序列，希尔排序算法的时间复杂度没有明显的差异。
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=10000
ht1
333682
261666
15
ht2
306649
253184
16
ht3
279746
253954
0
ht4
265227
267958
0

N=100000
ht1
5096795
4257586
63
ht2
4697147
4046190
62
ht3
4429964
4114525
63
ht4
3917957
3578357
47

N=1000000
ht1
75941566
65312129
1154
ht2
69536625
61435851
1061
ht3
67952651
63812420
999
ht4
65159058
60976081
936

N=10000000
ht1
1145131840
1015037491
18081
ht2
1816965129
1723263388
34991
ht3
1030483923
977174600
16162
ht4
914309790
854308146
13681
根据上表的结果可以看出，当增量序列为ht4时，希尔排序的效率最优，增量序列ht3次之，ht2也好于ht1说明奇数序列效率比偶数效率高。而且随着元素个数N的增大，该特征更明显。
六、 结束语
本文通过大量数据对希尔排序的增量序列进行初步的研究，得出结论：选取增量序列ht4=N/3+1,N/9+1,N/27+1,…,1进行希尔排序效率最高，而且性能稳定。

参考文献
[1]耿国华，《数据结构——C语言描述》,北京，高等教育出版社，2005.7
[2]李井润．一种基于统计的分段排序算法[J]．微计算机应用，2004，25(3)：274—279

附源代码：
#include<stdio.h>
#include<time.h>
#include<windows.h>
#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]<r[i-m])
{
r[0]=r[i];
exc++;
for(j=i-m;j>0&&r[0]<r[j];j-=m)
{
com++;
r[j+m]=r[j];
exc++;
}
com++;
r[j+m]=r[0];
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;
do
{
m=2*m;
ShellInsert(r,n,N/m,com,exc);//1 5 9 13 17
}while(m<N);
end_time =(long)GetTickCount();//结束时间
printf("***********希尔排序：***********\n");
printf("比较次数：%ld\n",com);
printf("移动次数：%ld\n",exc);
printf("执行时间：%d\n",end_time-start_time);
}

void ShellSort2(int *r,int n)//ht2增量序列排序
{
long start_time,end_time;
start_time =(long)GetTickCount();
int com=0,exc=0,m=1,k=1;
do{
m=2*m+1;
k++;
}while(m<=N);
do{
int p=1;
for(int i=0;i<k;i++)
p=p*2;
ShellInsert(r,n,p-1,com,exc);
k--;
}while(k>=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)//ht3增量序列排序
{
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<k;i++)
p=p*3;
ShellInsert(r,n,(p-1)/2,com,exc);
k--;
}while(k>=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)//ht4增量序列排序
{
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;
}