Java 冒泡排序完整實作：基礎版、優化旗標版與區域冒泡進階解析

冒泡排序核心思想

重複遍歷陣列，比較相鄰元素，逆序則交換。每輪遍歷將當前最大元素「冒泡」至未排序區域末端。時間複雜度 O(n²)，空間複雜度 O(1)，屬穩定排序。

基礎版實作

public class BubbleSort {
    /** 基礎冒泡排序：雙層迴圈，外層控制輪數，內層比較交換 */
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {           // 第 i 輪（共 n-1 輪）
            for (int j = 0; j < n - i; j++) {   // 未排序區域 0 ~ n-i
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] data = {2, 4, 76, 12, 34, 23, 86};
        System.out.println("排序前：" + Arrays.toString(data));
        bubbleSort(data);
        System.out.println("排序後：" + Arrays.toString(data));
        // 輸出：[2, 4, 12, 23, 34, 76, 86]
    }
}

優化一：旗標提前終止

若某輪遍歷未發生任何交換，說明陣列已有序，可提前結束。

public static void bubbleSortOptimized(int[] arr) {
    int n = arr.length;
    boolean swapped;
    for (int i = 1; i < n; i++) {
        swapped = false;
        for (int j = 0; j < n - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                swapped = true;
            }
        }
        if (!swapped) break; // 本輪無交換，已有序
    }
}

效能影響：最佳情況（已排序）從 O(n²) 降為 O(n)；最壞情況（逆序）仍為 O(n²)。

優化二：記錄最後交換位置（區域冒泡）

每輪遍歷中，記錄最後一次交換的位置 lastSwap，下一輪只需遍歷到該位置，因為其後元素已確定有序。

public static void bubbleSortRegion(int[] arr) {
    int n = arr.length;
    int lastSwap = n - 1;
    while (lastSwap > 0) {
        int currentSwap = 0;
        for (int j = 0; j < lastSwap; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                currentSwap = j; // 記錄最後交換位置
            }
        }
        lastSwap = currentSwap; // 下一輪邊界縮減至最後交換處
    }
}

優勢：對部分有序陣列（如尾部少數元素亂序）效能提升顯著，平均比較次數少於基礎版。

複雜度與效能總結

實務建議

• 教學/面試：掌握三種版本邏輯與優化原理。
• 生產代碼：勿手寫冒泡排序。使用 Arrays.sort()（雙軸快排 + 插入排序混合）或 Collections.sort()（TimSort），效能優越且經過充分測試。
• 小資料量/近乎有序：插入排序通常優於冒泡排序。
• 嵌入式/受限環境：若極度受限且資料量極小（<50），旗標版冒泡排序代碼最簡潔。

總結

冒泡排序是理解排序算法基石的絕佳切入點，透過「旗標提前終止」與「區域邊界縮減」兩大優化，可大幅改善近乎有序資料的表現。但實務開發中，請堅持使用標準庫排序，專注於業務邏輯而非重造輪子。