Shell排序的原理与集体实现

希尔排序因计算机科学家Donald L. Shell而得名，他在1959年发现了希尔排序算法。希尔排序基于插入排序，但是增加了一个新的特性，大大地提高了插入排序的执行效率。

依靠这个特别的实现机制，希尔排序对于多达几千个数据项的，中等大小规模的数组排序表现良好。希尔排序不像快速排序和其它时间复杂度为O(N*logN)的排序算法那么快，因此对非常大的文件排序，它不是最优选择。但是，希尔排序比选择排序和插入排序这种时间复杂度为O(N2)的排序算法还是要快得多，并且它非常容易实现。它在最坏情况下的执行效率和在平均情况下的执行效率相比没有差很多。

插入排序：复制的次数太多

由于希尔排序是基于插入排序的。回想一下在插入排序执行的一半的时候，标记符左边这部分数据项都是排过序的，而标记右边的数据项则没有排过序。这个算法取出标记符所指的数据项，把它存储在一个临时变量里。接着，从刚刚被移除的数据项的左边第一个单元开始，每次把有序数据项向右移动一个单元，直到存储在临时变量里的数据项能够有序回插。

下面是插入排序带来的问题。假设一个很小的数据项在很靠近右端的位置上，这里本来应该是值比较大的数据项所在的位置。把这个小数据项移动到在左边的正确位置上，所有的中间数据项都必须向右移动一位。这个步骤对每一个数据项都执行了将近N次的复制。虽不是所有数据项都必须移动N个位置，但是数据项平均移动了N/2个位置，这就是执行了N次N/2个移位，总共是N2/2次复制。因此，插入排序的执行效率是O(N2)。

如果能以某种方式不必一个一个地移动所有中间的数据项，就能把较小的数据项移动到左边，那么这个算法的执行效率就会有很大的改进。

N-增量排序

希尔排序通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项能大跨度地移动。当这些数据项排过一趟序后，希尔排序算法减小数据项的间隔再进行排序，依此进行下去。进行这些排序时数据项之间的间隔被称为增量，并且习惯上用字母H来表示。

现在有10个数据项，增量为4。在0、4和8号位置上的数据项已经有序了。

当对0、4和8号数据项完成排序之后，算法向右移一步，对1、5和9号数据项进行排序。这个排序过程持续进行，直到所有的数据项都已经完成了4－增量排序，也就是说所有间隔为4的数据项之间都已经排列有序。

在完成以4为增量的希尔排序之后，数组可以看成是由4个子数组组成：（0,4,8），（1,5,9），（2,6）和（3,7），这四个子数组内分别是完全有序的。这些子数组相互交错着排列，然而彼此独立。

注意，在这个例子中，在完成以4为增量的希尔排序后，所有元素离它在最终有序序列中的位置相差都不到两个单元。这就是数组“基本有序”的含义，也正是希尔排序的奥秘所在。通过创建这种交错的内部有序的数据项集合，把完成排序所必需的工作量降到了最小。

插入排序对基本有序的数组排序是非常有效的。如果插入排序只需要把数据项移动一位或者两位，那么算法大概需要O(N)时间。这样，当数组完成4-增量排序之后，可以进行普通的插入排序，即1-增量排序。4-增量排序和1-增量排序结合起来应用，比前面不执行4-增量排序而仅仅应用普通的插入排序要快得多。

减小间隔

上面已经演示了以4为初始间隔对包含10个数据项的数组进行排序的情况。对于更大的数组开始的间隔也应该更大。然后间隔不断减小，直到间隔变成1。

举例来说，含有1000个数据项的数组可能先以364为增量，然后以121为增量，以40为增量，以13为增量，以4为增量，最后以 1为增量进行希尔排序。用来形成间隔的数列被称为间隔序列。这里所表示的间隔序列由Knuth提出，此序列是很常用的。数列以逆向形式从1开始，通过递归表达式

h=3*b+1

来产生，初始值为1。

还有一些其他的方法也能产生间隔序列；后面会讲到这个问题。首先，来研究使用Kunth序列进行希尔排序的情况。

在排序算法中，首先在一个短小的循环中使用序列的生成公式来计算出最初的间隔。h值最初被赋为1，然后应用公式h=3*h+1生成序列1,4,13,40,121,364，等等。当间隔大于数组大小的时候，这个过程停止。对于一个含有1000个数据项的数组，序列的第七个数字，1093就太大了。因此，使用序列的第六个数字作为最大的数字来开始这个排序过程，作364-增量排序。然后，每完成一次排序全程的外部循环，用前面提供的此公式倒推式来减小间隔：

h=(h-1)/3

这个倒推的公式生成逆置的序列364,121,40,13,4,1。从364开始，以每一个数字作为增量进行排序。当数组用1-增量排序后，算法结束。

希尔排序比插入排序快很多，它是基于什么原因呢？当h值大的时候，数据项每一趟排序需要移动元素的个数很少，但数据项移动的距离很长。这是非常有效率的。当h减小时，每一趟排序需要移动的元素的个数增多，但是此时数据项已经接近于它们排序后最终的位置，这对于插入排序可以更有效率。正是这两种情况的结合才使希尔排序效率那么高。

注意后期的排序过程不撤销前期排序所做的工作。例如，已经完成了以40-增量的排序的数组，在经过以13-增量的排序后仍然保持了以40-增量的排序的结果。如果不是这样的话，希尔排序就无法实现排序的目的。

希尔排序的Java代码

class ArraySh{

private long[] theArray;

private int nElems;

public ArraySh(int max){

theArray=new long[max];

nElems=0;

}

public void insert(long value){

theArray[nElems]=value;

nElems++;

}

public void display(){

System.out.print("A=");

for(int j=0;j<nElems;j++)

System.out.print(theArray[j]+" ");

System.out.println("");

}

public void shellSort(){

int inner,outer;

long temp;

int h=1;

while(h<=nElems/3)

h=h*3+1;

while(h>0){

for(outer=h;outer<nElems;outer++){

temp=theArray[outer];

inner=outer;

while(inner>h-1 && theArray[inner-h]>=temp){

theArray[inner]=theArray[inner-h];

inner-=h;

}

theArray[inner]=temp;

}

h=(h-1)/3;

}

}

}

其他间隔序列

选择间隔序列可以称得上是一种魔法。至此只讨论了用公式h=h*3+1生成间隔序列，但是应用其他间隔序列也取得了不同程序的成功，只是一个绝对的条件，就是逐渐减小的间隔最后一定要等于1，因此最后一趟排序是一次普通的插入排序。

在希尔的原稿中，他建议初始的间距为N/2，简单地把每一趟排序分成了两半。因此，对于N=100的数组逐渐减小的间隔序列为50,25,12,6,3,1。这个方法的好处是不需要在不开始排序前为找到初始的间隔而计算序列；而只需要用2整除N。但是，这被证明并不是最好的数列。尽管对于大多数的数据来说这个方法还是比插入排序效果好，但是这种方法有时会使运行时间降到O(N2)，这并不比插入排序的效率更高。

这个方法的一个变形是用2.2而非2来整除每一个间隔。对于N=100的数组来说，会产生序列45,20,9,4,1。这比用2整除显著改善了效果，因为这样避免了某些导致时间复杂度为O(N2)的最坏情况的发生。不论N为何值，都需要一些额外的代码来保证序列的最后取值为1。这产生了和清单中所列的Knuth序列差不多的结果。

递减数列的另一个可能是

if(h<5)

h=1;

else

h=(5*h-1)/11;

间隔序列中的数字互质通常被认为很重要：也就是说，除了1之外它们没有公约数。这个约束条件使每一趟排序更有可能保持前一趟排序已排好的效果。希尔最初以N/2为间隔的低效性就是归咎于它没有遵守这个准则。

或许还可以设计出像如上讲述的间隔序列一样好的间隔序列。但是不管这个间隔序列是什么，都应该能够快速地计算，而不会降低算法的执行速度。

希尔排序的效率

迄今为止，除了在一些特殊的情况下，还没有人能够从理论上分析希尔排序的效率。有各种各样基于试验的评估，估计它的时间级从O(N3/2)到O(N7/6)。