• 什么是希爾排序
• C語言實現
  • 數組打印函數
  • 排序函數
  • 測試函數
  • 運行結果
• 參考資料

希爾排序的名稱源于它的發明者——唐納德·希爾（Donald Shell）。

希爾排序是另一種形式的插入排序，它神奇地突破了冒泡排序、直接選擇排序、直接插入排序等算法的二次時間界限，在時間復雜度上首次實現了質的突破。

希爾排序如此神奇，這源于它對插入排序兩個優點的綜合應用：

在數據量少的時候插入排序速度很快；

在數據幾乎有序的時候插入排序速度很快；

什么是希爾排序

我們通過一個例子解釋希爾排序使用的策略。假設我們要對隨機數組 A[16] 進行排序，其中的元素用 a0 ~ a15 表示。

一、 從 a0 開始，按照 1,2,3，…，8 報數，報相同數字的分為一組。即將 16 個數據分為 8 組：

[a0, a8],

[a1, a9],

[a2, a10],

[a3, a11],

[a4, a12],

[a5, a13],

[a6, a14],

[a7, a15]。

注意：這里說的是邏輯上的分組，不是真的把數據交換位置。在代碼實現上我們只要用跳躍的數組下標就可以。

這 8 組數據每一組都只包含兩個元素，通過插入排序可以快速完成（插入排序的第一個優點）。排序完成后的數組用 B[16] 表示；

二、從 b0 開始，按 1,2,3,4 報數。報相同數字的分為一組，這樣就將 B[16] 分為 4 組：

[b0, b4, b8, b12],

[b1, b5, b9, b13],

[b2, b6, b10, b14],

[b3, b7, b11, b15]。

這 4 組數據每一組中的元素個數比第一步要多一些，但是每一組都有一個特點：比較有序。比如第一組： b0 和 b8 是有序的，b4 和 b12 也是有序的。這樣我們就可以利用插入排序第二個優點，對每一組進行插入排序。第二步完成后的數組用 C[16] 表示；

三、從 c0 開始，按 1，2 報數。報相同數字的分為一組，這樣就將 C[16] 分為 2 組：

[c0, c2, c4, c6, c8, c10, c12, c14],

[c1, c3, c5, c7, c9, c11, c13, c15]。

這 2 組數據每一組中的元素個數比上一步又要多一些，但是它的有序程度也更明顯。比如第一組中的c0, c4, c8, c12 是有序的，c2, c6, c10, c14 也是有序的。這樣我們還是可以利用插入排序的第二個優點，對每一組進行插入排序；

四、對所有元素進行排序。雖然元素數量是這四步中最多的，但是這時候元素的有序程度也是最高的。

這樣我們就通過 4 組插入排序完成了對 16 個元素的排序工作。請注意，這 4 組中的每一組都有這樣一個特點：要么數據量很小（第一組），要么數據量越來越大但是有序程度越來越高（后三組）。

可以看到，希爾排序在數據量和數據有序程度上進行了折中安排。雖然進行了多次插入排序，但是由于插入排序是二次的而不是線性的，所以小規模的多次插入排序快于大規模的一次插入排序。

值得注意的是，希爾排序必須在最后一組進行完整的插入排序，否則結果一般不會正確。

總結上面的方法，我們得到希爾排序的一般策略：

希爾排序使用一個序列 h1h1，h2h2，h3h3，......，htht 叫做增量序列。只要 h1=1h1=1，任何增量序列都是可行的。不過，有些增量序列比另外一些增量序列要好（后文會說到）。在使用增量 hkhk 的一趟排序后，對于每一個 ii，我們有 a[i]≤a[i+hk]a[i]≤a[i+hk]，此時稱文件是hkhk - 排序 的。

hkhk - 排序 的一般做法是：

把 a1a1，a1+hka1+hk，a1+2hka1+2hk，......，分為一組；
把 a2a2，a2+hka2+hk，a2+2hka2+2hk，......，分為一組；
把 a3a3，a3+hka3+hk，a3+2hka3+2hk，......，分為一組；
......
......

把ahkahk，a2hka2hk，a3hka3hk，......， 分為一組。

一趟 hkhk - 排序 的作用就是對 hkhk 個獨立的子數組執行一次插入排序。

在增量序列的選擇上，比較流行的做法是使用Shell建議的序列：

ht=floor(N/2)ht=floor(N/2)
hk=floor(hk+1/2)hk=floor(hk+1/2)

也就是我們上面介紹的方法。

C語言實現

數組打印函數

void print_array(int a[], int len, int gap) {for(int i=0; i<len; ++i){printf("[%d]:%2d ", i, a[i]);if((i + 1) % gap == 0)printf("\n");}printf("\n\n"); }

這個函數是專門為希爾排序設計的。我想把排序的過程打印出來，那自然少不了分組。gap這個參數用來傳遞 hkhk - 排序 的 hkhk

因為有if((i + 1) % gap == 0)這個條件判斷，所以每打印 hkhk 個數就換行一次，所以看的時候要豎著看，每一縱列就是一組，一共有 hkhk 組。

如果不希望換行打印，則可以給gap傳一個比數組長度大的參數。

排序函數

這個是原原本本地按照希爾排序的步驟而寫的。

如果在編譯的時候定義了宏PRINT_PROCEDURE，則可以打印出排序的具體過程，對理解希爾排序非常有幫助。

代碼就不多說了，因為有詳細的注釋。

void shellsort(int arr[], int n) { //步長采用shell序列for (int gap = n / 2; gap > 0; gap /= 2) { #ifdef PRINT_PROCEDUREprintf("-------- gap = %d--------\n",gap);print_array(arr, n, gap); #endif for (int i = 0; i < gap; i++) { #ifdef PRINT_PROCEDURE printf("column %d :\n",i); // 對列i排序 #endiffor (int j = i + gap; j < n; j += gap) { // 每次加上步長，即按列排序。 // if 條件成立說明arr[j]需要插入到某個位置if (arr[j - gap] > arr[j]) { // 因為arr[j]會被前面的記錄覆蓋，所以先暫存int temp = arr[j]; int k = j - gap; // k指向arr[j-gap]，從后往前遍歷while (k >= 0 && arr[k] > temp) { arr[k + gap] = arr[k]; // arr[k]向后移動 k -= gap; } // 把arr[j]插入到arr[k]的后面arr[k + gap] = temp; #ifdef PRINT_PROCEDUREprintf("[%d] insert to [%d]\n", j, k+gap); #endif } }} #ifdef PRINT_PROCEDUREprintf("\n");print_array(arr, n, gap); #endif } }

趕緊寫個測試函數，看看排序的過程吧。

測試函數

#define DUMMY_GAP 100int main(void) {int array[] = {5,2,8,9,3,9,7,1,0,4,}; // 10個數print_array(array,sizeof(array)/sizeof(array[0]),DUMMY_GAP);shellsort(array, sizeof(array)/sizeof(array[0]));print_array(array,sizeof(array)/sizeof(array[0]),DUMMY_GAP);return 0; }

運行結果

從上圖可以看出，一共分成了5組（豎著看），對每一組都進行直接插入排序。

上圖是 hk=1hk=1 的情況，對所有元素進行排序。雖然元素數量是這3次中最多的，但是這時候元素的有序程度也是最高的。

【未完待續】

參考資料

《數據結構與算法分析（原書第2版）》（機械工業出版社，2004）

總結

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

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