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

標籤

2011年3月30日 星期三

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

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

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

範例代碼 : 

  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] = {251236452939229837};  
  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>

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

沒有留言:

張貼留言

網誌存檔

關於我自己

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