一.理論准備
希爾排序(Shell Sort)是插入排序的一種，是針對直接插入排序算法的改進，是將整個無序列分割成若干小的子序列分別進行插入排序，希爾排序並不穩定。該方法又稱縮小增量排序，因DL．Shell於1959年提出而得名。
基本思想：先取一個小於n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然後，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
希爾排序的時間性能優於直接插入排序的原因：
①當文件初態基本有序時直接插入排序所需的比較和移動次數均較少。
②當n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復雜度O(n)和最壞時間復雜度0(n2)差別不大。
③在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，後來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由於已經按di-1作為距離排過序，使文件較接近於有序狀態，所以新的一趟排序過程也較快。
因此，希爾排序在效率上較直接插人排序有較大的改進。
增量序列的選擇：Shell排序的執行時間依賴於增量序列。
好的增量序列的共同特征(查到的資料都這麼講)：
① 最後一個增量必須為1；
② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。
看到了這個，我想試試希爾排序，就學學。
代碼如下：
public class ShellSort {
public static void main(String[] args) {
int[] arr = new int[]{44,33,99,10,30,20,59,78,23,48};
System.out.print("排序前：");
for(int o: arr) {
System.out.print(o+" ");
}
System.out.println();
shellSort(arr);
System.out.print("排序後：");
for(int o: arr) {
System.out.print(o+" ");
}
System.out.println();
}
private static void shellSort(int[] arr) {
int j;
int len = arr.length;
for(int val=len>>1; val>0; val>>=1) {
//下面是對本次的所有分組做直接插入排序
for(int i=val; i<len; i++) {
int temp = arr[i];
/*
* 為什麼每次都用temp比較呢？
* 因為直接插入就是找到temp的合適位置。
* 為什麼temp<arr[j-val]這個條件可以放在for內呢？
* 因為原來的組內數據已經有序，找到位置就停止便是。
* 不甚理解的去看直接插入排序吧。
*/
for(j=i; j>=val&&temp<arr[j-val]; j-=val) {
/*
* 為什麼是arr[j-val]不是arr[j]呢？
* 因為j=i開始的，而且條件是j>=val&&temp<arr[j-val]
*/
arr[j] = arr[j-val];
}
/*
* 注意不是arr[i] = temp
* 直接插入排序也是這樣的。
* 為什麼呢？
* 因為j是位置，i是待插入元素
*/
arr[j] = temp;
}
}
}
}
三.問題
希爾排序一定正確麼？換句話說如何選取增量序列才能保證正確(包括長度、值)？是的，最後一次只要保證增量是1就ok(不管序列長度，只不過效率就低了)，若是序列只有1，那就是直接插入排序了，不知道對否。
