Java 經典排序：冒泡排序原理、優化與完整實作

算法核心思想

冒泡排序 通過重複遍歷陣列，比較相鄰元素並交換順序錯誤的配對，使較大元素逐漸「浮」至陣列末端。每輪遍歷確定一個最大值位置，下一輪範圍縮減一。

執行流程圖解

陣列：[6, 3, 8, 2, 9, 1]

1. 第 1 輪：5 次比較，9 浮至索引 4 → [3, 6, 2, 8, 1, 9]
2. 第 2 輪：4 次比較，8 浮至索引 3 → [3, 2, 6, 1, 8, 9]
3. 第 3 輪：3 次比較，6 浮至索引 2 → [2, 3, 1, 6, 8, 9]
4. 第 4 輪：2 次比較，3 浮至索引 1 → [2, 1, 3, 6, 8, 9]
5. 第 5 輪：1 次比較，2 浮至索引 0 → [1, 2, 3, 6, 8, 9]

標準實作

public class BubbleSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                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 sortOptimized(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]) { swap(arr, j, j + 1); swapped = true; }
        }
        if (!swapped) break; // 本輪無交換，已有序
    }
}

複雜度分析

適用場景

• 教學演示排序基本原理。
• 極小規模資料（n < 50）或近乎有序資料。
• 嵌入式系統記憶體極度受限、代碼尺寸敏感場景。

生產環境大規模排序請使用 Arrays.sort() (Dual-Pivot QuickSort / TimSort) 或 Collections.sort()。