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，因此最后一趟排序是一次普通的插入排序。
 &

补充：综合编程 , 其他综合 ,