程式扎記: [ 資料結構 小學堂 ] 排序 : 希爾排序

標籤

2010年11月23日 星期二

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

前言 : 
"希爾排序法" 是 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. 此排序法適用於資料大部分都已排序完成的情況.

範例代碼 : 

  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

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!