原理：

這個是基于插入排序的改進。將待排序的記錄數目減少，所以，我們需要采用跳躍分割策略：將相距某個分量的記錄組成一個子序列分別進行插入排序得到的結果是基本有序。

算法講解：

void ShellSort(SqList *L) {int i,j;int increment = L->length;do {increment = increment / 3 + 1; // 增量序列for( i = increment + 1; i<=L->length;i++) {if (L->r[i]<L->r[i-increment]) {// 需要將L->r[i]插入有序增量子表L->r[0] = L->r[i];for(j = i - increment;j>0&&L->r[0]<L->r[j];j-=increment)L->r[j+increment] = L->r[j]; // 記錄后移，查找插入位置L->r[j+increment] = L->r[0];}}} while (increment>1);}

1.程序開始，此時假設我們傳入的SqList 參數值為 length = 9，r[10] = {0,9,1,5,8,3,7,4,6,2}.請看圖

2.第四行，變量increment，初始值讓它等于待排序的記錄，9。

3.第5-19行是一個do循環，它終止條件是 increment 不大于 1 時。其實也是增量為1就停止循環。

4.第 7 行，這一句很關鍵，但也是難以理解的地方，我們后面還要談到它1，先放一放。這里執行后，increment = 9 / 3 + 1 = 4。

5.第 8-17 行是一個 for 循環，i 從 4 + 1 = 5 開始到 9 結束。

6.第 10 行，判斷 L.r[i]? 與 L.[i-increment]大小，L.r[5] = 3小于L.r[i-increment] = r[1] = 9,第 12 行，將L.r[5] = 3 贊存入L.r[0]。第 13-14 行的循環只是為了將L.r[1] = 9的值賦值給L.r[5]，由于循環的增量是 j -= increment，其實它就循環一次，此時 j = -3. 第 15 行，再將 L.r[0] = 3 賦值給 L.r[j+increment] = L.r[1] = 3.如圖，事實上，這一段代碼就干了一件事，就是將第 5 位的 3 和 第 1 位的 9 交換了位置。

?7.循環繼續，i = 6，L.r[6] = 7 > L.r[i - increment] = L.r[2] = 1，因此不交換兩組數據。如圖

8.循環繼續，i = 7，L.r[7] =? 4 < L.r[i-increment] = L.r[3] = 5,交換兩者數據。如圖

?9.循環繼續， i = 8，L.r[8] = 6 < L.r[i-increment] = L.r[4] = 8，交換兩者數據。如圖。

?

?10.循環繼續，i = 9，L.r[9] = 2 < L.r[i-increment] = L.r[5] = 9,兩者交換數據。注意，第 13 和 14 行是循環，此時還要繼續比較 L.r[5] 與 L.r[1] 的大小，因為 2 < 3，交換位置。

?

?最終第一輪循環后，數組的結果如下圖所示。我們的數字1,2等小數字基本已經在前兩位，而8,9等大數字都基本在最后，也就是說，通過這樣的排序，我們的整個序列基本有序。這就是希爾排序的精華所在，不是一步一步移動，而是跳躍式的前移，從而使沒次完成一輪循環后，整個序列就朝著有序堅實地邁進一步。

?11.我們繼續，在完成一輪do循環后，此時由于increment = 4 > 1因此我們需要繼續 do 循環。第 7 行 increment = 4 / 3 + 1 = 2。第 8 - 17 行 for 循環，i 從 2 + 1= 3 開始到 9 結束。當i = 3,4時，不用交換，當 i = 5 時，需要交換。

12. 此后， i = 6,7,8,9均不用交換。

13.再完成一輪do循環，increment = 2，繼續do循環，第七行得到 increment = 1，最后一次循環了。盡管 8-17 行 for 循環，i 從 2 到 9結束，但由于當前的序列更接近有序，可交換的數據更少了。最終完成排序。

?復雜度分析：

這里“增量”的選取就非常關鍵了。我們用 increment = increment? / 3 + 1；的方式選取增量，可究竟應該選取什么樣的增量才是最好，目前還是一個數學難題，迄今還沒有人找到一種最好的增量序列。不過大量研究表明，當增量序列為 ? 時，可以獲得不錯的效率，其時間復雜度為 要好于直接排序 O(n^2).需要注意的是，增量序列最后一個增量值必須等于 1 才行。另外，由于記錄是跳躍式的移動，希爾排序并不是一個穩定的排序算法。

總結

以上是生活随笔為你收集整理的希尔排序原理和算法图解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。