前言
本篇部落格是在伍迷兄的部落格基礎上進行的，其部落格位址點選就可以進去，裡面好部落格很多，我的排序算法都來自于此；一些資料結構方面的概念我就不多闡述了，伍迷兄的部落格中都有詳細講解，而我寫這些部落格隻是記錄自己學習過程，加入了一些自己的了解，同時也希望給别人提供幫助。
前提故事
騷年在上次與部落客進行了直接插入排序的讨論後，找到了部落客，說：“部落客，對于直接插入排序，我有重大的發現”，部落客想了想，就問：“什麼發現？”，騷年：“我發現了如下兩點”
1）當序列的個數比較少時，直接插入排序效率高；這個好了解，個數比較少，那麼插入的次數也就少了，部落客就說：“恩，這個發現不難，卻也需要細心”。
2）如果序列本身就是基本有序，那麼直接插入排序效率高；部落客：“嗯？”，騷年解釋道：“你看直接插入排序的核心代碼：”
for(int i=1; i<len; i++){
for(int j=i-1; j>=0&&arr[j]>arr[j+1]; j--){
swap(arr,j,j+1);
}
} 騷年接着道：“如果序列有序，那麼j>=0&&arr[j]>arr[j+1]條件就是不滿足的，插入操作就不會執行，效率自然就高了。”
部落客：“然後了？”。
騷年：“那麼我們是不是可以在這兩點上做點事，來提高直接插入排序在普通序列上的效率了？”。
上述兩個條件過于苛刻，現實中記錄少或者基本有序都屬于特殊情，有條件當然是好，條件不存在，我們創造條件，也是可以去做的；騷年與部落客進行了研究與讨論，我們可以對序列進行分組，分割成若幹個子序列，然後對每個子序列分别進行直接插入排序，當整個序列都基本有序時，注意隻是基本有序時，再對全體記錄進行一次直接插入排序。
此時一定有人開始疑惑了。這不對呀，比如我們現在有序列是{5,3,7,9,1,6,4,8,2}，現在将它分成三組，{5,3,7}， {9,1,6}，{4,8,2}，哪怕将它們各自排序排好了，變成{3,5,7}，{1,6,9}，{2,4,8}，再合并它們成 {3,5,7,1,6,9,2,4,8}，此時，這個序列還是雜亂無序，談不上基本有序，要排序還是重來一遍直接插入有序，這樣做有用嗎？需要強調一下， 所謂的基本有序，就是小的關鍵字基本在前面，大的基本在後面，不大不小的基本在中間，像{2,1,3,6,4,7,5,8,9}這樣可以稱為基本有序了。 但像{3,5,7,1,6,9,2,4,8}這樣的7在第三位，2在倒數第三位就談不上基本有序。
那麼問題就來了，我們分割待排序記錄的目的是減少待排序記錄的個數，并使整個序列向基本有序發展。而如上面這樣分完組後，就各自排序的方法達不到我們的要求。是以，我們需要采取跳躍分割的政策：将相距某個“增量”的記錄組成一個子序列，這樣才能保證在子序列内分别進行直接插入排序後得到的結果是基本有序而不是局部有序。
基本思想
将整個序列按照相距某個“增量”進行拆分，然後逐個對子序列進行直接插入排序，使得得到的結果基本有序，最後對基本有序的序列進行一次直接插入排序，使得整個序列有序
代碼實作
java實作
/**
* 希爾排序
* @param arr 目标序列
*/
public static void shellSort(int[] arr){
int len = arr.length;
for(int gap=len/2; gap>=1; gap=gap/2){ //拆分整個序列，元素間距為gap(也就是增量)
//對子序列進行直接插入排序
for(int i=gap+1; i<len; i++){
for(int j=i-gap; j>=0&&arr[j]>arr[j+gap]; j=j-gap){
swap(arr,j,j+gap);
}
}
}
} View Code
執行過程模拟
1）程式開始執行，初始序列為{5,3,7,9,1,6,4,8,2}，如下圖：
2）初始gap=len/2=4
2.1）i=gap=4，初始j=0；比較arr[j]與arr[j+gap],即arr[0]與arr[4],如下圖：
j=j-gap=-4，跳出，i++，i=5
2.2）i=5，j=i-gap=1，arr[1]=3 < arr[5]=6,不交換資料，如下圖：
j=j-gap=-3,跳出，i++,i=6
2.3)同理，當i=6，7時，序列如下圖：
2.4）當i=8時，序列如下：
那麼gap=4時，最終序列為
3）gap=gap/2=2
3.1)i=gap=2,j=i-gap=0,arr[0]=1 < arr[2]=4不交換，j=j-gap=-2，i++，此時序列為：
3.2）i=3，j=i-gap=1，arr[1]=3 < arr[3]=8,不交換，j=j-gap=-1，i++,此時序列為：
3.3）同理，i=4時：
3.4）i=5時：
3.5）i=6時：
3.6）i=7時：
3.7）i=8時：
4）gap=gap/2=1，此時
for(int gap=len/2; gap>=1; gap=gap/2){ //拆分整個序列，元素間距為gap(也就是增量)
//對子序列進行直接插入排序
for(int i=gap; i<len; i++){
for(int j=i-gap; j>=0&&arr[j]>arr[j+gap]; j=j-gap){
swap(arr,j,j+gap);
}
}
就是
//對子序列進行直接插入排序
for(int i=1; i<len; i++){
for(int j=i-1; j>=0&&arr[j]>arr[j+1]; j=j-1){
swap(arr,j,j+1);
}
} 相信大家都發現了，上面代碼就是我們的直接插入排序，那麼具體的模拟過程我也就不再贅述了，不懂的可以去看排序之直接插入排序
至此，整個序列就有序了。
難解之處
通過這段代碼的剖析，相信大家有些明白，希爾排序的關鍵并不是随便的分組後各自排序，而是将相隔某個“增量”的記錄組成一個子序列，實作跳躍式的移動，使得排序的效率提高。這裡“增量”的選取就非常關鍵了，本例中是以gap=gap/2的方式選取增量的，可究竟應該選取什麼樣的 增量才是最好，目前還是一個數學難題，迄今為止還沒有人找到一種最好的增量序列。不過大量的研究表明，當增量序列為dlta[k]=2t-k+1-1（0≤k≤t≤⌊log2(n+1)⌋）時，可以獲得不錯的效率。需要注意的是，增量序列的最後一個增量值必須等于1才行。