希爾排序，希爾排序算法

希爾排序，希爾排序算法

希爾排序：

一句話描述： 將數列分組。每組表示為 [ i,i+d,i+2d,i+3d,...i+kd ] 。每組都用插入排序。最後對整個數組進行一次插入排序。

增量序列希爾提出為：d1=n/2 , d2=d1/2 ...,最後一個增量等於 1

復雜度難以計算 

C++實現：

 1 //希爾排序
 2 //不穩定算法
 3 //時間復雜度：平均n^1.3  最壞：n^2
 4 //一句話描述： 將數列分組。每組表示為[i,i+d,i+2d,i+3d,...i+kd]。每組都用插入排序。最後對整個數組進行一次插入排序。
 5 //增量序列希爾提出為：d1=n/2 , d2=d1/2 ...,最後一個增量等於 1
 6 
 7 void ShellSort(int (&A)[10]){
 8     int d;
 9     for(d=10/2;d>1;d=d/2){
10         changeD(A,d);
11     }
12     InsertionSort(A);  //直接插入排序
13 }
14 
15 
16 void changeD(int (&A)[10],int d){
17     for(int j=0;j<d;j++){
18         for(int k=j+d;k<10;k=k+d){  //k為未整理數組 
19             int tmp=A[j+d];
20             for(int i=j;i>=0;i=i-d){  //i為 整理好的數組的最後一個
21                 if(tmp<A[i])
22                     Swap(A[i+d],A[i]);
23 
24             }
25         }
26     }
27 }