2010年12月6日 星期一

[ 資料結構 小學堂 ] 排序 : 改良氣泡排序法

前言 : 
由傳統泡沫排序法可以看出有一個缺點是不管資料是否以排序完成都固定會執行 n(n-1)/2 次, 而我們可以藉由在程式中加入一判斷式來加以判斷何時可以提前中斷程式, 又可以得到正確的資料, 來增加程式的執行效能. 

範例代碼 : 

  1. #include   
  2.   
  3. using namespace std;  
  4.   
  5. struct BenchMark {  
  6.     int swapTime;  
  7.     int verifyTime;  
  8. };  
  9. BenchMark advanceBubbleSort(int data[], int n) {  
  10.     int cnt = 0, vt=0, flag=0;  // flag 是用來判斷是否已完成排序並跳出的比較的迴圈  
  11.     BenchMark bm;  
  12.     for(int i=n-1; i>0; i--) {  
  13.         flag = 0;  
  14.         for(int j=0; j
  15.             vt++;  
  16.             if(data[j+1] < data[j]) {  
  17.                 int tmp = data[j+1];  
  18.                 data[j+1] = data[j];  
  19.                 data[j] = tmp;  
  20.                 cnt++;  
  21.                 flag++;  
  22.             }  
  23.         }  
  24.         if(flag==0) { // 完成排序, 故不需要 swap  
  25.             break;  
  26.         }  
  27.     }  
  28.     bm.swapTime = cnt;  
  29.     bm.verifyTime = vt;  
  30.     return bm;  
  31. }  
  32. void main(bool b) {  
  33.     if(b) {  
  34.         int data[6] = {2,5,9,7,6,8};  
  35.         cout<< "原始資料: " << endl;  
  36.         for(int i=0; i<6; i++) {  
  37.             printf("%2d ",data[i]);  
  38.         }  
  39.         printf("\n");  
  40.         BenchMark bm = advanceBubbleSort(data, 6);  
  41.         cout << "改良泡沫排序: " << endl;  
  42.         for(int i=0; i<6; i++) {  
  43.             printf("%2d ",data[i]);  
  44.         }  
  45.         printf("\n");  
  46.         printf("Swap time: %d\n", bm.swapTime);  
  47.         printf("Verify time: %d\n", bm.verifyTime);  
  48.     }  
  49. }  
執行效果 : 

原始資料:
2 5 9 7 6 8
改良泡沫排序:
2 5 6 7 8 9
Swap time: 4
Verify time: 12 <執行次數小於 n(n-1)/2, n=6 => 15>

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...