三大經典排序算法 Java 實現：冒泡、選擇、插入排序深度解析

算法複雜度總覽

1. 冒泡排序

核心思想：雙層迴圈比較相鄰元素，大者後移，每輪將最大值「冒泡」至末尾。可加入 swapped 標誌優化已有序情況。

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - i - 1; 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; // 提前終止
    }
}

2. 選擇排序

核心思想：每輪從未排序區間選出最小值，與區間首位交換。交換次數固定為 n-1，適合寫入成本高的存儲介質。

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

3. 插入排序

核心思想：維護有序前綴，將當前元素插入合適位置。對近乎有序資料極快（O(n)），是 Shell 排序、TimSort 基礎。

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

實戰建議

• 小規模資料（< 50）或近乎有序 → 插入排序
• 記憶體寫入敏感、不要求穩定 → 選擇排序
• 教學演示、極小資料集 → 冒泡排序
• 生產環境請直接使用 Arrays.sort()（雙軸快排 + TimSort 混合）