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

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

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

6 4 9 8 3 -> 比較6 > 4 : 6 與 4 交換
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次) 

4 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次) 

4 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. 此排序法適用於資料量小或有部分資料已經排序過.

範例代碼 : 

view plaincopy to clipboardprint?

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>

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