Like Share Discussion Bookmark Smile

J.J. Huang   2020-03-06   排序演算法   瀏覽次數:

排序演算法 | 泡沫排序

泡沫排序(英語:Bubble Sort)又稱為泡式排序,是一種簡單的排序演算法。它重複地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換,也就是說該數列已經排序完成。
這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端(升序或降序排列),就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣,故名「泡沫排序」。

泡沫排序演算法的運作如下:

  • 比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。
  • 對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對。這步做完後,最後的元素會是最大的數。
  • 針對所有的元素重複以上的步驟,除了最後一個。
  • 持續每次對越來越少的元素重複上面的步驟,直到沒有任何一對數字需要比較。

使用泡沫排序為一列數字進行排序的過程:

實作範例(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@Test
public void bubbleSort() {
    int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    // 統計比較次數
    int count = 0;
    // 第一輪比較
    for (int i = 0; i < arr.length - 1; i++) {
        // 第二輪比較
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交換位置
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
            count++;
        }
    }
    System.out.println(Arrays.toString(arr));
    System.out.println("一共比較了:" + count + "次");
}

結果:

1
2
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
一共比較了:105次

這段程式相信大家都能夠寫出來,一般泡沫排序也就是這樣寫。但是這段程式有個缺點,就是當排序過程中已經將數組元素排序完成,但此時它仍然會去比較,這就做了無用功了,所以我們可以通過一個boolean變量來優化這段代,上面的程式中我們已經得出了比較次數為105次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
@Test
public void bubbleSort() {
    int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    // 統計比較次數
    int count = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        boolean flag = true;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交換位置
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = false;
            }
            count++;
        }
        if(flag) {
            break;
        }
    }
    System.out.println(Arrays.toString(arr));
    System.out.println("一共比較了:" + count + "次");
}

結果:

1
2
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
一共比較了:95次

我們首先在開始循環時定義了一個boolean變量為true,然後如果元素之間進行了交換,就將值置為false。所以,我們就可以通過這個boolean變量來判斷是否有元素進行了交換。如果boolean變量為true,則證明沒有元素進行交換,那麼久說明此時的數組元素已經完成排序,那麼跳出外層循環即可,否則就繼續排序。通過結果也可以看出,比較次數確實是​​減少了很多。


註:以上參考了
維基百科-泡沫排序
演算法筆記
程式员必须掌握的核心算法有哪些?
程式员那些必须掌握的排序算法(上)
程式员那些必须掌握的排序算法(下)