Java 陣列排序三大演算法：快速排序、氣泡排序、選擇排序完整比較

1. 內建快速排序 Arrays.sort()

JDK 使用雙軸快速排序（基本型別）與 TimSort（物件），平均 O(n log n)，效能最佳、穩定（物件版）、一行解決。

int[] arr = {2, 0, 1, 4, 5, 8};
Arrays.sort(arr); // 升序
// 輸出: 0 1 2 4 5 8

2. 氣泡排序

相鄰元素兩兩比較，大者後移，每趟將最大值「氣泡」至末尾。時間複雜度 O(n²)，教學用途為主。

public static int[] bubbleSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = 0; j < a.length - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp;
            }
        }
    }
    return a;
}

3. 選擇排序

每趟在未排序區間找最小值（或最大值），交換至區間首部。同 O(n²)，但交換次數最少（O(n)）。

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

效能比較表（隨機 10,000 整數）

原始碼修正說明

原文提供的氣泡/選擇排序程式碼有語法錯誤（mian、testMethod(arr) 缺型別、max 未宣告等），上方已修正為可編譯版本。

進階補充

• 插入排序：近乎有序資料極快，JDK 對小陣列（<47）內部切換使用。
• 合併排序：穩定 O(n log n)，需 O(n) 額外空間，Arrays.sort(Object[]) 即為 TimSort（合併+插入混合）。
• 平行排序：Java 8+ Arrays.parallelSort() 利用 Fork/Join 框架多核加速大陣列。

最佳實踐建議

1. 生產代碼永遠使用 Arrays.sort() 或 Collections.sort()。
2. 面試/教學時能手寫三種基本排序並說出複雜度、穩定性。
3. 特殊場景（如整數範圍已知）考慮計數排序、基數排序 O(n)。