另一種寫法

上一篇博文希爾排序（一）中的代碼是基于希爾排序的原理，“直譯”過來的。還有一種更簡單的寫法：

void shellsort_2(int a[], int n) { int j, gap;for (gap = n / 2; gap > 0; gap /= 2) { #ifdef PRINT_PROCEDUREprintf("-------- gap = %d--------\n",gap);print_array(a, n,gap); #endiffor (j = gap; j < n; j++)//從數組第 gap個元素開始 ，直到 n-1 { if ( a[j - gap] > a[j] )//每個元素與自己組內的數據進行直接插入排序 { int temp = a[j]; int k = j - gap; while (k >= 0 && a[k] > temp) //&&優先級更低 { a[k + gap] = a[k]; // a[k]向后移動 ，騰出一個空位k -= gap; }// 考察空位前面的元素a[k+gap] = temp; //插入 #ifdef PRINT_PROCEDUREprintf("[%d] insert to [%d]\n", j, k+gap);print_array(a, n,gap); #endif }}} }

對希爾排序的改進

希爾排序的運行時間依賴于增量序列的選擇。 舉個例子，如果使用 Shell 建議的序列，假使上一個增量為 4，那么當前的增量就是 2。因為2是4的因子，所以對于上一輪已經比較過的元素，這一輪會重復比較，這就造成了時間的浪費。更好的增量序列選擇是增量序列中的任何2個元素都是互素的。目前已有學者提出了一些更有效的增量序列，這里僅展示其中的2個。

Hibbard （希巴德）序列

Hibbard（希巴德）序列：

1,3,7,...,2k?11,3,7,...,2k?1 （kk 為大于 00 的自然數）

使用 Hibbard 增量的希爾排序，其最壞情形的運行時間為 Θ(n3/2)Θ(n3/2)；
其平均情形的運行時間被認為是 O(n5/4)O(n5/4)（基于模擬結果）。

Sedgewick （塞奇威克）序列

已知的最好的增量序列是由 Sedgewick（塞奇威克） 提出的： 1,5,19,41,109,....1,5,19,41,109,.... 這個序列中的項交替地取自以下2個序列：

1,19,109,505,2161,...,9?(4k?2k)+11,19,109,505,2161,...,9?(4k?2k)+1 (k=0,1,2,3,...)(k=0,1,2,3,...)

5,41,209,929,3905,...,2k+2(2k+2?3)+15,41,209,929,3905,...,2k+2(2k+2?3)+1 (k=0,1,2,3,...)(k=0,1,2,3,...)

使用 Hibbard 增量的希爾排序平均運行時間猜測為O(n7/6)O(n7/6)，最壞情形為O(n4/3)O(n4/3)。

改進后的C語言代碼

void shell_sort_improved(int A[], int N, int inc_seq[]) {int inc = 0; int max_inc_idx = 0; int i,j,k,tmp;while (inc_seq[ max_inc_idx + 1 ] < N) max_inc_idx++; //找到最大的且小于N的那個增量 for (i = max_inc_idx; i >= 0; --i){ inc = inc_seq[i]; #ifdef PRINT_PROCEDUREprintf("-------- gap = %d--------\n",inc); #endif for (j = inc; j < N; ++j) { if( A[j-inc] > A[j] ){tmp = A[j]; k = j - inc; while (k >= 0 && A[k] > tmp) { A[ k + inc ] = A[k]; // A[k]向后移動 inc個位置，騰出一個空位k -= inc; // 繼續考察空位前面的元素 } A[k + inc] = tmp; // tmp 插入到k的后面 #ifdef PRINT_PROCEDUREprintf("[%d] insert to [%d]\n", j, k+inc); #endif }} } }

最后一個參數是增量序列。

完整代碼及測試

#include <stdio.h> #include <stdlib.h> #include <time.h>#define PRINT_GAP 10 #define ARRAY_LEN 100void print_array(int a[], int len, int gap) // 用于打印數組 {for(int i=0; i<len; ++i){printf("[%2d]:%2d ", i, a[i]);if((i + 1) % gap == 0)printf("\n");}printf("\n\n"); }void shell_sort_improved(int A[], int N, int inc_seq[]) {int inc = 0; int max_inc_idx = 0; int i,j,k,tmp;while (inc_seq[ max_inc_idx + 1 ] < N) max_inc_idx++; //找到最大的且小于N的那個增量 for (i = max_inc_idx; i >= 0; --i){ inc = inc_seq[i]; #ifdef PRINT_PROCEDUREprintf("-------- gap = %d--------\n",inc); #endif for (j = inc; j < N; ++j) { if( A[j-inc] > A[j] ){tmp = A[j]; k = j - inc; while (k >= 0 && A[k] > tmp) { A[ k + inc ] = A[k]; // A[k]向后移動 inc個位置，騰出一個空位k -= inc; // 繼續考察空位前面的元素 } A[k + inc] = tmp; // tmp 插入到k的后面 #ifdef PRINT_PROCEDUREprintf("[%d] insert to [%d]\n", j, k+inc); #endif }} } } int main(void) {printf("\n");int array[ARRAY_LEN]; srand((unsigned int) time(NULL)); //設置隨機數種子// 產生100個隨機整數，范圍在 [0, 100]for(int i=0; i<ARRAY_LEN; ++i){array[i] = rand() % 101;}print_array(array,sizeof(array)/sizeof(array[0]),PRINT_GAP);int Sedgewick_seq[] = {1, 5, 19, 41, 109};shell_sort_improved(array, sizeof(array)/sizeof(array[0]),Sedgewick_seq);print_array(array,sizeof(array)/sizeof(array[0]),PRINT_GAP);return 0; }

運行結果如下圖：

【完】

參考資料

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

總結

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

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