[ 資料結構 小學堂 ] 排序 : 希爾排序

前言 : 
"希爾排序法" 是 D.L. Shell 在 1959 年 7 月所發明的一種排序法, 而該排序法是直接以發明者命名. 其排序原理有點像是插入排序法, 但它可以減少資料搬移的次數. 排序的原則是將資料區分成特定間隔的幾個小區塊, 接著以插入排序法排完區塊內的資料後再漸漸減少間隔的距離. 

演算法說明 : 
請考慮右邊元素, 並使用 Shell 演算法由小到大排序 : 6 9 2 3 4 7 5 1 
第一次掃描 : 間隔為 8/2=4 : 6 9 2 3 4 7 5 1 
6 4 -> 4 6 
9 7 -> 7 9 
2 5 -> 2 5 
3 1 -> 1 3 
掃描完結果 : 4 7 2 1 6 9 5 3 

第二次掃描 : 間隔為 8/2/2=2 : 4 7 2 1 6 9 5 3 
4 2 6 5 -> 2 4 5 6 
7 1 9 3 -> 1 3 7 9 
掃描完結果 : 2 1 4 3 5 7 6 9 

第三次掃描 : 間隔為 8/2/2/2 = 1 : 2 1 4 3 5 7 6 9 
2 1 4 3 5 7 6 9 -> 1 2 3 4 5 6 7 9 
掃描完結果 : 1 2 3 4 5 6 7 9 

希爾演算法分析 : 

1. 任何情況下的情況複雜度為 O(n^(3/2))
2. 希爾排序與插入排序一樣, 都是穩定排序.
3. 只需一個額外空間, 空間複雜度最佳.
4. 此排序法適用於資料大部分都已排序完成的情況.

範例代碼 : 

view plaincopy to clipboardprint?

1. #include   
2. #include   
3.   
4. using namespace std;  
5.   
6. struct BenchMark {  
7.     int swapTime;  // Swap Time  
8.     int verifyTime;  // Verify Time  
9.     double cTime;  // Consumed Time  
10. };  
11.   
12. BenchMark shellSort(int data[], int n) {  
13.     int cnt=0, vt=0, jump = n/2, j;  
14.     BenchMark bm;     
15.     bool in = false;  
16.     while(jump>0) {  
17.         for(int i=jump; i
18.             for(int k=i; k
19.                 j = i-jump;  
20.                 in = false;  
21.                 while(j>=0 && data[j+jump]
22.                     in = true;  
23.                     cnt++;  
24.                     vt++;  
25.                     int tmp = data[j+jump];  
26.                     data[j+jump] = data[j];  
27.                     data[j] = tmp;  
28.                     j-=jump;  
29.                 }  
30.                 if(!in) {  
31.                     vt++;  
32.                 }  
33.             }  
34.         }  
35.         jump = jump/2;  
36.     }  
37.     bm.swapTime = cnt;  
38.     bm.verifyTime = vt;  
39.     return bm;  
40. }  
41. void _inputData(int data[], int size) {  
42.     for(int i=0; i
43.         cout << "請輸入第" << i+1 << " 個元素: ";  
44.         cin >> data[i];  
45.     }  
46. }  
47.   
48. void _showData(int data[], int size) {  
49.     for(int i=0; i
50.         printf("%2d ", data[i]);  
51.     }  
52.     printf("\n");  
53. }  
54.   
55. #define SHELL_DATA_SIZE 5  
56. void main(bool b) {  
57.     if(b) {  
58.         int data[SHELL_DATA_SIZE];  
59.         _inputData(data, SHELL_DATA_SIZE);  
60.         printf("原始資料為: ");  
61.         _showData(data, SHELL_DATA_SIZE);  
62.         BenchMark bm = shellSort(data, SHELL_DATA_SIZE);  
63.         cout << "希爾排序: " << endl;  
64.         _showData(data, SHELL_DATA_SIZE);  
65.         printf("Swap time: %d\n", bm.swapTime);  
66.         printf("Verify time: %d\n", bm.verifyTime);  
67.     }  
68. }  

執行結果 : 

請輸入第1 個元素: 4 <依序輸入元素>
請輸入第2 個元素: 8
請輸入第3 個元素: 9
請輸入第4 個元素: 1
請輸入第5 個元素: 3
原始資料為: 4 8 9 1 3
希爾排序:
1 3 4 8 9
Swap time: 4
Verify time: 15