基于java的資料結構學習手記12-使用Knuth序列的希爾排序

        希爾排序因計算機科學家Donald L.Shell而得名，他在1959年發現了希爾排序算法。希爾排序基于插入排序，但是增加了一個新的特性，大大地提高了插入排序的執行效率。希爾排序算法的代碼短而簡單，而且它在最壞情況下的執行效率和在平均情況下的執行效率相比沒有差很多。

         插入排序算法：插入排序算法在執行到中間的時候，标記符指向的數的左邊都是有序的，而标記右邊的都是沒有排序的。這個算法取出标記符指向的資料項，從其左邊第一個資料項開始從右到左掃描，凡是比它大的數字都右移一位，最後插入。插入排序的問題是，假設一個很小的資料項在很靠近右邊的位置上，在移動這個資料項的過程中要複制太多中間資料項，平均每個資料移動複制達N/2，插入排序執行效率為O(N2).

       如果某個算法能夠不必一個一個移動所有中間資料項，就能把較少的資料項移動到左邊，那麼這個算法的執行效率就有很大的改進。

        希爾排序就是基于這種思想設計的。

希爾排序引入N-增量排序的概念，上圖所示的為增量為4時的排序，即隻對0，4，8排序，間隔為4.這步操作完成後指針右移一位對1，5，9排序，然後對2，6排序，最後是3，7排序。形成彼此交錯互相獨立的排序。

 減少間隔：當完成了間隔為4個排序後，再接着做間隔為1的插入排序，完成後則整個數組都會有序了。這個縮減間隔序列的數值是由knuth序列決定，即是公式3h+1序列（1，4，13，40，。。。）保證3h+1<ｍａｘＩｔｅｍｓ（數組中資料項個數）得到最大的h值，然後按照h=(h-1)/3遞減，直到h=1為止。

          需要指出的是，實際的計算中不沒有完全按照以上的排序順序，具體看圖示：

代碼 ：

Code:

1. package highSort;  
2. //demonstrate shell sort  
3. //  
4. class ArraySh   
5. {  
6.     private long[] theArray;           //ref to array theArray  
7.     private int nElems;                //number of data items  
8. //-------------------------------------------------------------  
9.     public ArraySh(int max) {  
10.       theArray=new long[max];  
11.       nElems=0;// TODO Auto-generated constructor stub  
12.     }  
13.     //------------------------------------------------------------  
14.     public void insert(long value)    //put element into array  
15.     {  
16.         theArray[nElems]=value;       //insert it  
17.         nElems++;                     //increment size  
18.     }  
19. //-------------------------------------------------------------  
20.     public void display()             //display each items of the array  
21.     {  
22.         System.out.print("A=");  
23.         for(int j=0;j<nElems;j++)  
24.             System.out.print(theArray[j]+" ");  
25.         System.out.println(" ");  
26.     }  
27. //-------------------------------------------------------------  
28.     public void shellSort()  
29.     {  
30.         int inner=0,outer=0;  
31.         long temp=0;  
32.         int h=1;                    //find initial value of h  
33.         while(h<=nElems/3)          //1,4,13,40,121,...  
34.             h=h*3+1;  
35.         while(h>0)  
36.         {  
37.         for(outer=h;outer<nElems;outer++)  
38.             {  
39.                 temp=theArray[outer];  
40.                 inner=outer;  
41.               while(inner>h-1&&theArray[inner-h]>=temp)  
42.                 {  
43.                 theArray[inner]=theArray[inner-h];  
44.                 inner-=h;  
45.                 }  
46.             theArray[inner]=temp;  
47.              }  
48.             h=(h-1)/3;  
49.          }  
50.      }  
51. }  

Code:

1. package highSort;  
2. public class ShellSortApp {  
3.     public static void main(String[] args) {  
4.         // TODO Auto-generated method stub  
5.          int maxSize=1000;  
6.          ArraySh arr;  
7.          arr=new ArraySh(maxSize);  
8.          for(int j=0;j<maxSize;j++)  
9.          {  
10.              long n=(int)(java.lang.Math.random()*1500);  
11.              arr.insert(n);   
12.          }  
13.          arr.display();  
14.          arr.shellSort();  
15.          arr.display();  
16.     }  
17. }  

随機生成1000個整數，進行希爾排序。