希尔排序算法设计思想研究

谢　婷（1.马鞍山市委党校，安徽 马鞍山243011；2马鞍山电视大学，安徽 马鞍山243011）

希尔排序算法设计思想研究

谢婷1，2
（1.马鞍山市委党校，安徽 马鞍山243011；2马鞍山电视大学，安徽 马鞍山243011）

根据对希尔排序算法原理的研究分析，指出希尔算法的执行时间是受文件大小、扫描次数等因素影响，其中影响最大的是增量序列的选取，通过实验证明，增量序列为N/3+1，N/9+1，N/27+1…，1时，程序排序效率比使用序列N/2，N/4，N/8，…，1要高。

希尔排序；算法；增量序列；时间复杂度

随着计算机信息技术的普及，算法也已成为计算机学科的重要研究对象。算法这一词汇是由数学家al-Khwarizmi的名字音译过来的，直到1936年图灵机这一现代计算机的基本模型出现后，算法的概念才算明确起来：算法就是按部就班地解决一个问题或完成一个目标的过程［1］。排序在算法中占有很重要的地位，排序算法在数据处理领域中是一种最常用的非数值算法，在计算机信息处理、数据库操作、数据分析等方面起着重要的作用。希尔排序算法是Donald.L. Shell于1959年提出的一种插入排序算法。希尔算法所占用的内存少，排序速度快，这就使得这种排序算法在记录较多时更具有使用价值。

一、希尔排序算法原理

希尔排序算法［2］：首先存在排列记录R1，R2，…RN；在完成排序以后，它们的关键码是有序的：K1＜= K2＜=…＜=KN。用一个辅助的增量序列ht，ht-1，…，h0来控制这个排序的过程，其中h0=1，t为程序的扫描次数｀；适当选择增量可以显著地减少排序时间，当t=1时，这个算法退化为直接插入排序法。

步骤1：［设置s循环］对s=t，t-1，…，0实施步骤2；然后结束这个算法。

步骤2：［设置j循环］设置h←hs，并对h＜j＜=N实施步骤3到步骤6（使用直接插入法来对隔开h个位置的记录进行排序，使得1＜=i＜=N-h，Ki＜=Ki+h）。

步骤3：［设置i，K，R］置i←j-h，K←Kj，R←Rj。

步骤4：［比较K：Ki］若K＞=Ki，则转到步骤6。

步骤5：［移动Ri，i减值］置Ri+h←Ri，然后i←ih。若i＞0，则转回到步骤4。

步骤6：［R进入Ri+h］置Ri+h←R。

二、希尔排序算法实现

希尔排序也叫做“减少增量的排序”，因为每次扫描都是通过一个增量h来确定，使得我们对相距h个单位的记录进行排序。希尔排序算法的实现如表1所示，最初有16个记录进行排序，设其增量序列的取值为8，4，2，1。首先设置增量h=8，将这16个记录分成8组，两两一组即（R1，R9），（R2，R10），…，（R8，R16）。分别对每组记录进行排序，使得我们进到表的第3行，这一操作称为“第一次扫描”。注意记录R11150已经同记录R3511交换了位置；记录R5918和记录R7886这两条记录都跳到右边去了。现在减小增量设置h= 4，把得到的记录重新分成4个组，每4个一组，即（R1，R5，R9，R13），…，（R4，R8，R12，R16），并再次分别对每组进行排序，这是“第二次扫描”，使得我们进入到表的第4行。第三次扫描再次减小增量设h=2，将得到的记录分为2组，对各有8个记录的两个组进行排序，然后进行第四次扫描，通过对所有的16个记录进行排序来完成整个过程。

希尔算法的代码如下：

表1　增量为8，4，2，1的Shell排序

三、希尔算法的分析

希尔算法在初排序时，增量h取值较大，即间隔较大，子序列较多，每个序列中的记录数目较少，所以子序列中用直接插入排序较快，随着增量h减小即间隔变小，子序列中记录数目增多，但由于已按上一个间隔排过序，记录接近有序状态，所以新的一趟排序过程也较快，在做最后一趟时，所有的排序码几乎有序了，大大提高了排序速度。

希尔算法的执行时间与5个因素有关：文件大小即排序的记录数N，扫描次数即增量的个数t，增量序列ht，ht-1，…，h0，比较次数A，移动次数B。其中关键字的比较次数在这里又是重要因素，而关键字的比较次数又受着增量序列的影响，所以希尔算法研究的核心就是增量序列ht，ht-1，…，h0如何选取，才能使得希尔算法执行时间最短。

定理［2］：如果增量序列ht，ht-1，…，h0，满足条件：hs+1modhs=0，对于t-1＞s＞=0，当排序记录个数N很大时，希尔算法的运行时间不能比O（N1。5）更小。定理中整除性条件意味着，在每种（hs+1/hs）有序排列都是同等可能意义的。然而实践证明，当N很大并且增量序列取值不满足这个整除性条件时，算法的执行时间会更短，时间效率会更高。例如当增量序列选取…8，4，2，1时，在奇数和偶数位置上键值不相关时，希尔排序最后增量h为1时记录移动次数O（N3/2），而当增量序列选取为…7，5，3，1时，最后增量h为1时记录移动次数最多为2N次，排序时间得到明显改善。所以我们有理由认为增量序列选取奇数序列比选取偶数序列要好，但并不一定是最好。理论上说，如果一个k有序的文件被h排序，则它保持为k有序。这一理论表明选取互素增量进行排序是可行的。

文中选取如下几种方式进行验证：⑴常用增量序列：N/2，N/4，N/8，…，1，易于简单程序实现。⑵Hibbard序列［3］：2k-1，这样得到的序列增量类似于奇数序列。 ⑶增量序列：N/3+1，N/9+1，N/27+1，…，1，这样得到的序列不满足整除条件。

四、实践验证

选取三组增量序列：

⑴ht1=N/2，N/4，N/8，…，1

⑵ht2=2k-1，…15，7，3，1

⑶ht3=N/3+1，N/9+1，N/27+1，…，1

代入希尔排序程序［4］，用随机生成函数随机产生三组大数量的无符号整数作为待排序记录的关键字，分别用上述三种增量序列对各组待排序序列进行排序，记录每个排序过程的比较次数、移动次数以及执行时间。

1.保持文件大小即排序的记录数N不变

当N=100000，用随机函数生成三组随机数，分别代入上述三种增量序列对其进行希尔排序实验。记录实验过程中的比较次数、移动次数和执行时间。测试结果记录在表2：

表2　N值固定时三组随机数据在不同增量序列下的测试结果

2.待排序列的记录个数增加

记录元素个数N的值从小到大变化（N=10000，100000，1000000，10000000）时，分别取三种增量序列代入同样的希尔排序程序进行实验，得到结果如表3：

表3　不同元素个数三种增量序列测试结果

根据表2表3的测试的结果来看，可以得出如下结论：

⑴对于记录数相同的三组随机生成的整数序列，在三种增量序列下排序中的比较次数、移动次数以及执行时间差别并不是很大。我们可以认为对于待排序序列的记录数相同情况下，这三种增量序列，希尔排序算法的时间复杂度没有明显的差异。

⑵希尔算法受增量序列影响较大，选取恰当的h序列能缩短程序的执行时间。

⑶增量序列为N/3+1，N/9+1，N/27+1…，1时相对于其它两种排序效率最优，随着记录个数的增多，优化效果越明显。同时也印证了不满足整除条件依然可以取得最优时间复杂度。特别要指出的是，ht3并不是唯一的最佳增量序列。

⑷奇数增量序列效率比偶数的要高。

［1］黄林鹏.基于归纳的算法设计思想［J］.程序员，2006（4）：56-58.

［2］DONALE E.Knuth计算机程序设计艺术（第3卷）排序与查找［M］.苏运霖，译.北京：国防工业出版社，2002：78-89.

［3］A.A.PAPERNOV G.V.Stasevich Problemy Peredachi Informatsii［M］.English translation in？Problems of Information Transmission Springer Publishing House.1965：81-98.

［4］刘瑞新.Visual C++面向对象程序设计教程［M］.北京：机械工业出版社，2004：79-88.

Research on the Design Idea of Shell Sorting Algorithm

Xie Ting1，2
（1.Ma＇anshan Mmunicipal Party Committee Party School，Ma＇anshan Anhui 243011，China；2.Ma＇anshan radio and Television University，Ma＇anshan Anhui 243011，China）

Based on the analysis of the research on the shell sort algorithm，the paper points out that Shell algorithm execution time is affected by the file size，number of scans and other factors，of which the influence is the largest increment series selection.Proved by experiments，the algorithm runs much better if it uses the sequence for N/3+1，N/9+1，N/27+1...，1 rather than the sequence of N/4，N/2，N/8，...，1.

Shell sort；algorithm；incremental sequence；time complexity

O223

A

1672-0547（2016）02-0111-02

2016-03-02

谢婷（1975-），女，安徽马鞍山人，马鞍山市委党校（马鞍山电视大学）讲师，硕士，研究方向：计算机信息技术、网络应用。