切換
舊版
前往
大廳
主題

簡單又明瞭 最基礎的泡沫排序法(Bubble sort)

魔化鬼鬼 | 2020-05-24 00:02:46 | 巴幣 1004 | 人氣 865

前言.

    學測考完後,實做了一些之前聽過的排序演算法,像我面試有回答出快速排序法的原理,但我從來都沒有真正的寫過,所以找了時間自己寫寫看(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;
            }
        }
    }
}



創作回應

更多創作