【演算法】Java 實作氣泡排序法（Bubble Sort）

日期：


一、概述

氣泡排序法是最簡單的排序方式之一。以遞增排序為例，做法是從一連串資料的第一項開始，與後一項比大小，並將較大的資料往後面交換。接著第二項再與第三項相比，依此類推。反覆交換後，最大的資料便會移動到最後一項。

此時再將範圍縮小到從第一項到倒數第二項，進行下一回合操作，直到排序完成。由於資料宛如氣泡般慢慢浮到正確的位置，因而得名。

二、排序過程

假設我們有一些數值資料：5、3、9、7、1，則第一回合的排序過程如下。

第一回合排序結果為：3、5、7、1、9，最大值已經移動到最後一個位置。第二回合所參與元素的位置範圍是從第一個到倒數第二個。排序過程如下。

第二回合排序結果為：3、5、1、7、9，第二大值已經移動到倒數第二個位置，也就是參與元素範圍的最後一個。第三回合的排序過程如下。

第三回合排序結果為：3、1、5、7、9，第四回合的排序過程如下。

第四回合排序結果為：1、3、5、7、9。由於下一回合所參與的元素不足兩個，無法進行比較，因此排序到此為止。


三、程式實作

氣泡排序法的實作並不複雜。由於它有交換元素的動作，我們先準備對應的程式碼。

private static void swap(int[] array, int index1, int index2) {
    int tmp = array[index1];
    array[index1] = array[index2];
    array[index2] = tmp;
}

接著開始撰寫排序程式。下面的 endIndex 變數是該回合所參與元素的最後一個位置。我們用 for 迴圈來控制執行的回合數，讀者可注意到，回合數等於元素數量減一。

public static void sort(int[] data) {
    for (int endIndex = data.length - 1; endIndex > 0; endIndex--) {
        // TODO
    }
}

在這個 for 迴圈中要實作的是每個回合的比較與交換過程。此處藉由內層的 for 迴圈，搭配 currentIndex 變數，在該回合所參與的元素範圍中移動。

public static void sort(int[] data) {
    for (int endIndex = data.length - 1; endIndex > 0; endIndex--) {
        for (int currentIndex = 0; currentIndex < endIndex; currentIndex++) {
            if (data[currentIndex] > data[currentIndex + 1]) {
                swap(data, currentIndex, currentIndex + 1);
            }
        }
    }
}

在 currentIndex 移動的過程中，我們會比較當前元素與後一項的元素，若前面的較大，就跟後面交換。由於比較的動作需要兩個元素才可進行，故 currentIndex 最大只能到 endIndex 的前一個位置，這便是內層迴圈執行條件如此定義的原因。

以下為氣泡排序法的完整程式碼
https://gist.github.com/ntub46010/38cf39b766c1dcdddd3e461ee7d04ba1


四、時間複雜度

根據第二節的示意圖，5個元素會有4個回合的比較與交換過程。第一回合比較4次、第二回合比較3次，直到第四回合比較1次。總比較次數為 4 + 3 + 2 + 1 = 10 次。

我們歸納出，n個元素需比較 (n - 1) + (n - 2) + ... + 1 次。根據數學上等差級數的公式，計算得

   (1 + 2 + ... + n) - n
= [n(1 + n) / 2] - n
= (n² - n) / 2

因此氣泡排序法的時間複雜度為 O(n²)。

 

五、穩定排序

假設一串數值資料中有相同值，比方說有兩個「3」，一個在比較前面，一個在比較後面。當它們在排序過程中移動到相鄰的位置並被比較，前面的3並不會被交換到後面的3的後方，導致相對位置改變，因此氣泡排序法屬於穩定排序。

留言

張貼留言