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

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

範例代碼 : 

view plaincopy to clipboardprint?

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>