冒泡排序演算法原理與 Java 實作完整指南

一、演算法核心思想

冒泡排序透過重複遍歷陣列，比較相鄰元素並交換順序，使較大（或較小）元素像氣泡一樣逐漸「浮」至陣列末端。屬於原地排序、穩定排序。

二、時間與空間複雜度

三、標準 Java 實作（遞減序）

public class BubbleSort {
    public static void sortDesc(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            // 每輪將當前最大值推至末端，已排區間 [n-i, n-1] 無需再比較
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] < arr[j + 1]) { // 遞減：前小於後則交換
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    swapped = true;
                }
            }
            if (!swapped) break; // 本輪無交換 → 已有序
        }
    }

    public static void main(String[] args) {
        int[] data = {8, 19, 88, 16, 34, 3, 10, 21};
        sortDesc(data);
        System.out.println(Arrays.toString(data)); // [88, 34, 21, 19, 16, 10, 8, 3]
    }
}

四、關鍵優化點解析

1. 外層迴圈上界 n - 1 - i：每輪確定一個最大值，減少比較次數。
2. swapped 旗標提前終止：若某輪無交換，代表陣列已有序，直接跳出。
3. 穩定性保證：僅在 arr[j] < arr[j+1] 時交換，相等元素不交換，保持相對順序。

五、變體：雞尾酒排序

雙向冒泡（左→右推最大、右→左推最小），對「小數值在右端」的近似有序陣列效能較佳，但最差仍為 O(n²)。

六、適用場景與替代方案

• 教學/面試/極小資料集（n < 50）：程式碼簡潔、易理解。
• 生產環境排序：請優先使用 Arrays.sort()（雙軸快排 + 歸併，O(n log n)）或 Collections.sort()。

七、常見錯誤自查

1. 內層迴圈上界寫錯（漏減 i）→ 多做無效比較、甚至越界。
2. 忘記 swapped 優化 → 已有序陣列仍跑完 O(n²) 輪。
3. 交換邏輯錯誤（如未用暫存變數直接 a=b; b=a;）。