Java 排序算法實現與複雜度分析：冒泡、選擇、插入排序詳解

通用說明

以下實現針對 int[]，原地排序，返回同一陣列引用。實際開發請優先使用 Arrays.sort() (雙軸快排/TimSort，O(n log n)、穩定)。

1. 冒泡排序

public static int[] bubbleSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        boolean swapped = false;
        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;
                swapped = true;
            }
        }
        if (!swapped) break; // 已有序提前結束
    }
    return a;
}

• 時間複雜度：最好 O(n) (已有序)，平均/最差 O(n²)。比較次數固約 n(n-1)/2。
• 空間複雜度：O(1)。
• 穩定性：穩定 (相等元素不交換)。

2. 選擇排序

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;
}

• 時間複雜度：始終 O(n²)，與輸入無關。比較 n(n-1)/2，交換最多 n-1 次。
• 空間複雜度：O(1)。
• 穩定性：不穩定 (交換可能改變相等元素相對順序)。

3. 插入排序

public static int[] insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
    return a;
}

• 時間複雜度：最好 O(n) (已有序)，平均/最差 O(n²) (逆序)。
• 空間複雜度：O(1)。
• 穩定性：穩定。
• 優勢：小數據量/近乎有序數據極快，常作快排/歸併排序小分區閾值 (如 Arrays.sort() 閾值 47)。

複雜度對比總結

進階提示

• Java 7+ Arrays.sort() 基本類型用雙軸快排，對象用 TimSort (歸併+插入混合)。
• 並行排序 Arrays.parallelSort() (JDK 8+) 利用 Fork/Join 多核加速。
• 自定義比較實現 Comparator 或 Comparable。