Java 資料結構與演算法：冒泡排序 Bubble Sort 完整實作與複雜度分析

演算法核心思想

冒泡排序透過 N 輪 遍歷，每輪將未排序區域的最大元素「冒泡」至正確位置。第 1 輪定最大值於末端，第 2 輪定次大值於倒數第二，以此類推。

標準實作（含註解版）

package al;

public class BubbleSort {
    /**
     * 冒泡排序
     * @param array 待排序陣列（原地排序）
     * 時間複雜度：O(n²)
     * 空間複雜度：O(1)
     * 穩定性：穩定
     */
    public void sort(int[] array) {
        int n = array.length;
        // 外層迴圈：控制排序輪數，共 n-1 輪
        for (int i = 0; i <= n - 1; i++) {
            // 內層迴圈：未排序區域 0 ~ n-1-i
            // 每輪結束後，最大元素已沉至 n-1-i 位置
            for (int j = 0; j < n - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    // 交換相鄰逆序對
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        BubbleSort sorter = new BubbleSort();
        int[] elements = {14, 77, 21, 9, 10, 50, 43, 14};

        System.out.print("排序前：");
        printArray(elements);

        sorter.sort(elements);

        System.out.print("排序後：");
        printArray(elements);
        // 輸出：9 10 14 14 21 43 50 77
    }

    private static void printArray(int[] arr) {
        for (int v : arr) System.out.print(v + " ");
        System.out.println();
    }
}

執行過程圖解（以 [5, 3, 8, 4, 2] 為例）

初始：[5, 3, 8, 4, 2]
第1輪：比較交換 → [3, 5, 4, 2, 8]  (8 冒泡到末端)
第2輪：               → [3, 4, 2, 5, 8]  (5 定位)
第3輪：               → [3, 2, 4, 5, 8]  (4 定位)
第4輪：               → [2, 3, 4, 5, 8]  (3 定位)
完成：[2, 3, 4, 5, 8]

複雜度分析

優化方向

1. 旗標提前終止：若某輪無交換，陣列已有序，break 跳出外層迴圈。
2. 記錄最後交換位置：下一輪內層迴圈邊界縮減至最後交換索引，減少無效比較。
3. 雞尾酒排序：雙向冒泡（左→右冒最大，右→左冒最小），對「海龜問題」（小元素在右端需多輪移至左端）有改善。

教學價值與實務定位

• 教學核心：理解「原地排序」、「穩定性」、「雙層迴圈邊界控制」、「交換邏輯」。
• 面試考點：手寫正確邊界（j < n-1-i）、優化旗標、複雜度分析、穩定性證明。
• 生產禁用：絕不在生產代碼使用。Java Arrays.sort() 採用雙軸快排 + TimSort 混合策略，效能碾壓 O(n²) 算法。

總結

冒泡排序是演算法入門的經典切入點，透過「比較-交換-邊界縮減」核心模式，建立對排序基本操作的直觀理解。掌握其優化思路（旗標、邊界記錄）有助於理解插入排序、快速排序等進階算法的改進邏輯。