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

算法核心思想

冒泡排序是最基礎的交換排序算法。其形象比喻：較小的關鍵字如氣泡逐步上浮，較大的關鍵字如石塊下沉。每一輪遍歷都會將當前無序區間的最大值「沉底」到正確位置。

算法流程

1. 從第一個元素開始，相鄰兩兩比較
2. 若前者大於後者，交換位置
3. 一輪結束後，最大元素移至末尾
4. 下一輪比較範圍縮減 1，重複上述過程
5. 直到無序區間長度為 1，排序完成

複雜度分析

Java 實現：通用 Comparable 版本

public static <T extends Comparable<T>> void bubbleSort(T[] array) {
    int n = array.length;
    for (int i = n - 1; i >= 1; i--) {          // 控制輪數，每輪確定一個最大值
        for (int j = 0; j < i; j++) {            // 無序區間遍歷
            if (array[j].compareTo(array[j + 1]) > 0) {
                T temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

Java 實現：基本類型優化版

public static void bubbleSort(int[] array) {
    int n = array.length;
    boolean swapped;
    for (int i = n - 1; i > 0; i--) {
        swapped = false;
        for (int j = 0; j < i; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;  // 提前終止優化：本輪無交換說明已有序
    }
}

測試驗證

public static void main(String[] args) {
    int[] data = {5, 6, 8, 4, 2, 4, 9, 0};
    System.out.println("排序前: " + Arrays.toString(data));
    bubbleSort(data);
    System.out.println("排序後: " + Arrays.toString(data));
    // 輸出: [0, 2, 4, 4, 5, 6, 8, 9]
}

教學價值與適用場景

• 教學首選：邏輯直觀，適合初學者理解排序基本概念、雙重迴圈控制、交換操作
• 微型數據集：n < 50 時，因無遞歸開銷、分支預測友好，實際速度可能優於快排
• 近乎有序數據：配合 swapped 標誌，最好情況 O(n) 線性時間完成
• 嵌入式/受限環境：極小代碼體積、零額外內存，適合資源極度受限場合

常見面試追問

1. 為什麼冒泡排序是穩定的？
2. 如何優化冒泡排序？（雙向冒泡、記錄最後交換位置）
3. 冒泡 vs 選擇 vs 插入，三者本質區別？
4. 能否用冒泡排序實現降序？如何修改？

總結

冒泡排序雖非生產環境主流選擇，但作為「排序算法入門磚」，其思想精髓——相鄰比較交換、有序區間逐步擴展——貫穿於快速排序、希爾排序等進階算法中。熟練掌握其變體與優化，是演算法功力的重要標誌。