程式扎記: [ 資料結構 小學堂 ] 排序 : 氣泡排序法

標籤

2010年12月6日 星期一

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

前言 : 
氣泡排序法又稱交換排序法, 是由觀察水中氣泡變化構思而成, 氣泡隨著水深壓力而改變. 氣泡在水底時, 水壓最大, 氣泡最小 ; 當慢慢浮上水面時, 發現氣泡由小漸漸變大. 氣泡排序法的比較方式是由第一個元素開始, 比較相鄰元素大小, 若大小順序有誤, 則對調後在進行下一個元素的比較. 如此掃描過一次之後, 就可以確保最後一個元素是位於正確的順序. 接著再逐步進行第二次掃描, 直到完成所有元素的排序為止. 

泡沫排序範例 : 
以下我們利用 6,4,9,8,3 數列的排序過程來解釋氣泡排序演算流程 : 
第一次掃描 : (比較4次) 

6 4 9 8 3 -> 比較6 > 4 : 6 與 4 交換
6 9 8 3 -> 比較6 < 9 : 不須交換
4 6 9 8 3 -> 比較 9 > 8 : 9 與 8 交換
4 6 8 9 3 -> 比較 9 > 3 : 9 與 3 交換 得第一次掃描結果 4 6 8 3 9

第二次掃描 : (比較3次) 

6 8 3 9 -> 比較 4 < 6 : 不須交換
4 6 8 3 9 -> 比較 6 < 8 : 不須交換
4 6 8 3 9 -> 比較 8 > 3 : 8 與 3 交換得第二次掃描結果 4 6 3 8 9

第三次掃描 : (比較2次) 

6 3 8 9 : 比較 4 < 6 : 不須交換
4 6 3 8 9 : 比較 6 > 3 : 6 與 3 交換得第三次掃描結果 4 3 6 8 9

第四次掃描 : (比較1次) 

4 3 6 8 9 : 比較 4 > 3 : 4 與 3 交換得第四次掃描結果 3 4 6 8 9


氣泡法分析 : 

1. 最壞情況及平均情況均需比較 : (n-1) + (n-2) + (n-3) + ... + 3 + 2 +1 = n(n-1) / 2 次 ; 時間複雜度為 O(n^2), 最好情況只需要完成一次掃描, 發現沒有做交換的動作則表示已經排序完成, 所以只做了 n-1 次比較, 時間複雜度為 O(n).
2. 由於泡沫排序為相鄰兩者互相比較對調, 並不會更改其原來排序的順序, 所以是穩定排序法.
3. 只需一個額外的空間, 所以空間複雜度為最佳.
4. 此排序法適用於資料量小或有部分資料已經排序過.

範例代碼 : 

  1. #include   
  2.   
  3. using namespace std;  
  4.   
  5. struct BenchMark {  
  6.     int swapTime;  
  7.     int verifyTime;  
  8. };  
  9. BenchMark traditionalBubbleSort(int data[], int n) {  
  10.     int cnt = 0, vt=0;  
  11.     BenchMark bm;  
  12.     for(int i=n-1; i>0; i--) {  
  13.         for(int j=0; j
  14.             vt++;  
  15.             if(data[j+1] < data[j]) {  
  16.                 int tmp = data[j+1];  
  17.                 data[j+1] = data[j];  
  18.                 data[j] = tmp;  
  19.                 cnt++;  
  20.             }  
  21.         }  
  22.     }  
  23.     bm.swapTime = cnt;  
  24.     bm.verifyTime = vt;  
  25.     return bm;  
  26. }  
  27. void main(bool b) {  
  28.     if(b) {  
  29.         int data[6] = {6,5,9,7,2,8};  
  30.         cout<< "原始資料: " << endl;  
  31.         for(int i=0; i<6; i++) {  
  32.             printf("%2d ",data[i]);  
  33.         }  
  34.         printf("\n");  
  35.         BenchMark bm = traditionalBubbleSort(data, 6);  
  36.         cout << "傳統泡沫排序: " << endl;  
  37.         for(int i=0; i<6; i++) {  
  38.             printf("%2d ",data[i]);  
  39.         }  
  40.         printf("\n");  
  41.         printf("Swap time: %d\n", bm.swapTime);  
  42.         printf("Verify time: %d\n", bm.verifyTime);  
  43.     }  
  44. }  
執行結果 : 
原始資料:
6 5 9 7 2 8
傳統泡沫排序:
2 5 6 7 8 9
Swap time: 7
Verify time: 15 <搜尋次數為 5+4+3+2+1 = 15>

補充說明 :
[資料結構 小學堂] 排序 : 改良氣泡排序

沒有留言:

張貼留言

網誌存檔

關於我自己

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