前言.
學測考完後，實做了一些之前聽過的排序演算法，像我面試有回答出快速排序法的原理，但我從來都沒有真正的寫過，所以找了時間自己寫寫看(6成時間看著螢幕發呆...)，泡沫、快排、合併，趁剛寫完還有一點記憶的時候寫下來，就當作是上資工系前的準備吧~
正文.
今天來講解的是排序演算法中最基礎最基礎的-Bubble sort，中文有人說氣泡排序法、泡沫排序法，都可以。之所以叫泡沫排序就是因為在排序時，陣列的值會像泡泡一樣往上跑，一個一個浮上來，聽起來很抽象？我來一步步地解釋一下泡沫排序的原理：
如果我們要由小排到大
假設我們有一個長度為5陣列，陣列的值如下
arr[5] = {8,5,4,5,1}
泡沫排序法會比較前後的值，倘若前者 > 後者，則前後對調
所以泡沫排序的第一次迴圈運作會是這樣：
1.
|8|5| 4 5 1
8>5 所以前後對調
變成5 8 4 5 1
2.
5|8|4| 5 1
8>4所以前後對調
變成 5 4 8 5 1
3.
5 4 |8|5| 1
8>5所以前後對調
變成 5 4 5 8 1
4.
5 4 5 |8|1|
8>1所以前後對調
變成 5 4 5 1 8
這樣第一輪就完成了，有沒有發現最大值8跑到最後了？這就是為什麼他叫泡沫排序的原因！照這樣的規律，最大值會一個一個出現在後方，如同泡泡一樣，一個一個浮出。
此時的8就是已經排序好的狀態了，現在要做的就是把前面東西都給他泡沫完成，也就是說我們只要處理第1個到第4個的數值，第5個已經不用管了。
(雖然很簡單，不過我再示範一次，因為我了解初學程式的迷惘)
1.
|5|4| 5 1 8
5>4所以前後對調
變成 4 5 5 1 8
2.
4 |5|5| 1 8
5沒有>5所以不動
3.
4 5 |5|1| 8
5>1所以前後對調
變成4 5 1 5 8
而因為8已經排序好了，所以不用考慮他了
這樣就又完成了第二輪的泡沫排序，很簡單吧？照這規律下去就可以推出第三輪、第四輪的順序了！
第三輪結果：4 1 5 5 8
第四輪結果：1 4 5 5 8
這樣排序就完成了！
有了上面的概念後就可以開始稍微停下來，自己嘗試寫寫看了，由於泡沫排序的規律十分直覺，所以非常適合初學者來練習。
不過天下沒有白吃的午餐，如此簡單直白的排序法，一定有其缺陷，就是執行速度，倘若資料只有數百筆，可能還綽綽有餘，但是遇到數萬甚至數億筆，那可能要跑到天荒地老！事實上，在資訊領域有個專門表示執行效率的名詞-時間複雜度(Time complexity)，符號為O()，而泡沫排序的平均時間複雜度為O(n^2)，什麼概念呢？另一個排序法-快速排序法的時間複雜度為O(n log(n))，如果數字夠大，這幾乎是拋物線跟斜直線的差距阿！還是不懂？沒關係我有更直白的方式
這是我用java寫的氣泡排序和合併排序(平均時間複雜度跟快速排序一樣的排序法)
跑一個長度為100萬的隨機整數陣列
分別為0.186秒和1763.614秒(大約30分鐘) 怎麼好像有點星爆?
這樣就明白了吧！
下面是我用Java寫的程式碼
可能不是很精簡
有興趣的就自己看看吧
| public static void bubbleSort(int[] arr, int beginI, int endI){ int maxIndex = endI+1; int temp; while(maxIndex > beginI){ maxIndex--; for(int i = beginI;i < maxIndex; i++){ if(arr[i] > arr[i+1]){ temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; } } } } |
達人
