[C 範例代碼] 排序算法 : 希爾排序 - 改善的插入排序法

前言 : 
用希爾排序對數字進行排序. 

技術要點 : 
希爾排序是在直接排序的基礎上做的改進, 也就是將要排序的序列按固定增量分成若干組, 等距離者在同一組中, 然後在組內進行直接排序. 這裡的固定增量從 n/2 (n 為數組元素個數) 開始, 以後每次縮小到原來一半. 

範例代碼 : 

view plaincopy to clipboardprint?

1. #include   
2. #include   
3. #include   
4.   
5. using namespace std;  
6. int _shellSort(int *s, int n) {  
7.     int tmp, j, d, count=0;   
8.     d  = n/2;  
9.     while(d>0) {  
10.         for(int i=d; i
11.             j = i-d;  
12.             if(j>=0) {  
13.                 tmp = s[i];  
14.                 while((j>=0) && (tmp < s[j])) {                     
15.                     count++;  
16.                     s[j+d] = s[j];  
17.                     j = j-d;  
18.                 }                 
19.                 s[j+d] = tmp;                 
20.             }  
21.         }  
22.         d = d/2;  
23.     }  
24.     return count;  
25. }  
26.   
27. void main() {  
28.     int a[10] = {25, 12, 36, 45, 2, 9, 39, 22, 98, 37};  
29.     printf("The original order: \n");  
30.     for(int i=0; i<10; i++)  
31.         printf("%2d ", a[i]);  
32.     printf("\n");  
33.     int c = _shellSort(a, 10);  
34.     printf("After 希爾插入法 sorting: \n");  
35.     for(int i=0; i<10; i++)  
36.         printf("%2d ", a[i]);  
37.     printf("\nTotal swap time:%d\n", c);  
38. }  

執行結果 : 

The original order:
25 12 36 45 2 9 39 22 98 37
After 希爾插入法 sorting:
2 9 12 22 25 36 37 39 45 98
Total swap time:11 <減少了swap次數, 如果使用直接插入法, 需要17次的swap>

補充說明 :  
* [ 資料結構 小學堂 ] 排序 : 希爾排序