冒泡排序算法原理與 Java 實現

算法核心思想

冒泡排序通過重複遍歷數組，比較相鄰元素，順序錯誤則交換。每一輪將當前未排序部分的最大值「冒泡」到末端。時間複雜度 O(n²)，空間複雜度 O(1)，屬於穩定排序。

詳細步驟

1. 比較相鄰元素，前者大則交換。
2. 對第 0 到 n-1 的每對相鄰元素執行步驟 1，完成後最後一個元素為最大值。
3. 針對前 n-1 個元素重複上述過程，每輪減少一個已排序元素。
4. 若某輪無任何交換，說明已有序，可提前終止（優化）。

動態演示

Java 代碼實現（含優化標誌）

public class BubbleSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            // 內層循環範圍逐輪縮小
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break; // 本輪無交換，已有序
            printStep(arr, i + 1);
        }
    }

    private static void printStep(int[] arr, int round) {
        System.out.print("第 " + round + " 輪: ");
        for (int v : arr) System.out.print(v + "\t");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] scores = {67, 69, 75, 87, 89, 90, 99, 100};
        System.out.println("原始: " + Arrays.toString(scores));
        sort(scores);
        System.out.println("最終: " + Arrays.toString(scores));
    }
}

執行結果示例

原始: [67, 69, 75, 87, 89, 90, 99, 100]
第 1 輪: 67	69	75	87	89	90	99	100
第 2 輪: 67	69	75	87	89	90	99	100
... (提前終止)
最終: [67, 69, 75, 87, 89, 90, 99, 100]

對於已近乎有序的數據，優化版冒泡排序接近 O(n)；但對於大規模亂序數據，建議使用快速排序、歸併排序或 JDK 內置 Arrays.sort() (Dual-Pivot Quicksort / TimSort)。