Java 選擇排序與冒泡排序：原理、代碼實現、複雜度對比與優化變體

一、選擇排序

核心思想

每一輪從未排序區間選出最小（或最大）元素，與未排序區間首位元素交換。共進行 n-1 輪。

過程圖解（升序）

初始：[64, 25, 12, 22, 11]
第1輪：選出 11 ↔ 交換 64 → [11, 25, 12, 22, 64]
第2輪：選出 12 ↔ 交換 25 → [11, 12, 25, 22, 64]
第3輪：選出 22 ↔ 交換 25 → [11, 12, 22, 25, 64]
第4輪：選出 25 ↔ 交換 25 → [11, 12, 22, 25, 64]（已有序）

代碼實現

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        if (minIdx != i) {
            int tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }
    }
}

特性總結

• 時間複雜度：最好/最壞/平均均為 O(n²)（雙重循環固定）。
• 空間複雜度：O(1) 原地排序。
• 穩定性：不穩定（交換可能改變相等元素相對順序）。
• 交換次數：最少，≤ n-1 次，適合「寫入成本高」場景（如 Flash 存儲）。

二、冒泡排序

核心思想

相鄰元素兩兩比較，大的「冒泡」到右端。每輪將當前最大元素固定到未排序區間末尾。可加入有序標記提前終止。

過程圖解（升序）

初始：[64, 25, 12, 22, 11]
第1輪：64↔25, 64↔12, 64↔22, 64↔11 → [25, 12, 22, 11, 64]
第2輪：25↔12, 25↔22, 25↔11     → [12, 22, 11, 25, 64]
第3輪：22↔11                     → [12, 11, 22, 25, 64]
第4輪：12↔11                     → [11, 12, 22, 25, 64]

代碼實現（含優化）

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

特性總結

• 時間複雜度：平均/最壞 O(n²)，最好 O(n)（已有序時）。
• 空間複雜度：O(1)。
• 穩定性：穩定（僅交換嚴格大於的相鄰元素）。
• 交換次數：較多，接近 O(n²)。

三、深度對比表

四、進階變體

• 雞尾酒排序：冒泡雙向改進，奇數輪左→右，偶數輪右←左，減少「烏龜」（小數在右端）移動距離。
• 堆排序：選擇排序的優化版，利用堆結構將「選最小」從 O(n) 降為 O(log n)，整體 O(n log n)，但不穩定。

五、常見排序算法複雜度速查

算法        平均時間    最壞時間    空間    穩定
插入排序     O(n²)      O(n²)      O(1)   ✓
冒泡排序     O(n²)      O(n²)      O(1)   ✓
選擇排序     O(n²)      O(n²)      O(1)   ✗
快速排序     O(n log n) O(n²)      O(log n) ✗
堆排序       O(n log n) O(n log n) O(1)   ✗
歸並排序     O(n log n) O(n log n) O(n)   ✓
希爾排序     O(n^1.3)   O(n²)      O(1)   ✗
基數排序     O(nk)      O(nk)      O(n+k) ✓

六、工程建議

1. 生產代碼禁用 O(n²) 排序：直接用 Arrays.sort()（雙軸快排/歸並混合）或 Collections.sort()（TimSort），穩定且高性能。
2. 教學/面試：掌握兩者邊界條件（空數組、單元素、已有序、逆序）、穩定性證明、優化思路（冒泡加標記、選擇排序雙向選極值）。
3. 特定場景：嵌入式/存儲受限環境寫入極其昂貴時，可考慮選擇排序或循環排序。

理解基礎排序的原理與優缺點，是掌握高級算法、優化系統性能的基石。