經典排序演算法——冒泡排序
- 2019 年 10 月 7 日
- 筆記
冒泡排序的原理
冒泡排序的原理是從第一個數字開始，依次讓相鄰的兩個數字進行比較，按照從大到小或從小到大的順序進行交換(如果是升序排列就把小的放前面，如果降序排列就把大的放前面)。
第一趟比較後，就把最大的的數字放在最後一個位置(假設按照升序排列)，然後進行第二趟比較，依次進行相鄰數字比較，第二趟比較後次大的數字放在了倒數第二個位置。
進行n-1（n代表待排序的數字個數）趟比較後（最後只剩一個無需比較），數字即為有序排列。
圖解展示冒泡過程
假設要排列的數字為 3 1 4 2 ，當進行第一趟排序時，如下圖所示（其中i表示數組的下標）
第一趟排序執行完後，數組中最大的數字4已找到，並放在數組的最後一後位置，所以後續比較無需再跟最後一個比較。下面看第二趟排序過程，如下圖
第二趟排序執行完，數組的次大數字3已找到，並放在數組的倒數第二的位置。此時由於我們選取的排列數據巧合，第三大的數字2也放在了倒數第三的位置，但按照我們比較邏輯，此時並不知道第三大數字已經找到，所以還會進行第三趟比較。如下圖所示
按照我們的邏輯，當第三趟比較執行完後，第三大的數字2已找到並放在倒數第三位的位置。剩下最後一個數字1無需再比較它本身的位置就是它應該所在的位置。
我們可以發現，當有4個數字時，只需進行3趟排序即可將無序數字變為有序，而每趟比較都會比上一次少比較一次(因上一趟比較已經確定了一個較大數字位置)
另外，在我們例子中，第三趟比較前數字已經處於正確的序列，所以無需再進行後續比較（當然我們剛好只比較三趟，如果有5個或更多數字，則可以省去後續比較）
下面看一下具體程式碼實現
1 public static void bubbleSort(int array[]){ 2 int temp = 0; 3 for (int i = 0; i < array.length - 1; i++) { 4 //有n個數據，只需要n-1趟排序即可 5 boolean flag = true; 6 for(int j=0;j<array.length -1 -i ;j++){ 7 if(array[j] > array[j+1]){ 8 flag = false; 9 temp = array[j]; 10 array[j] = array[j+1]; 11 array[j+1] = temp; 12 } 13 } 14 if(flag){ 15 break; 16 } 17 } 18 }
程式碼分析
1）第一層for循環用於確定進行幾趟比較，前面我們分析過，只需進行n-1趟比較即可
2）第二層for循環用於從第1個數字開始，依次跟相鄰數字進行比較。每進行一趟比較後，就可少比較一位數字
3）在進行第二層循環比較時，設定一個標誌位flag，用於標示是否進行了數字交換，如果一次都沒有交換，說明此時數字已經有序，無需進行後續趟的比較
總結
冒泡排序需要記住兩個關鍵點，一是比較的趟數n-1（最後一個數字無需比較），二是每進行一趟比較後就會確定一個較大的數字位置，後續趟的比較次數會少一次。還有一點是優化點，當在比較過程中數字的正確順序已經產生後，無需再進行後續趟的比較。
