Java 經典排序算法實現：插入、選擇、冒泡排序全解析

前言

排序算法是計算機科學基石。本文提供三種基礎排序的 Java 實現，並分析時間複雜度與優化思路。

1. 插入排序

將無序區元素逐個插入有序區適當位置。

public static int[] insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        // 將大於 key 的元素右移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

特點：近乎有序數據表現優異（O(n)），原地排序，穩定。

2. 選擇排序

每輪從無序區選出最小元素，與無序區首位交換。

public static int[] selectSort(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;
        }
        // 交換
        int tmp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = tmp;
    }
    return arr;
}

特點：交換次數最少（O(n)），但比較次數固定 O(n²)，不穩定。

3. 冒泡排序

基礎版

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

優化版：提前終止

public static int[] bubbleSortOptimized(int[] arr) {
    boolean swapped;
    for (int i = 0; i < arr.length - 1; i++) {
        swapped = false;
        for (int j = arr.length - 1; j > 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;  // 本輪無交換，說明已有序
    }
    return arr;
}

特點：優化後最好情況 O(n)，原地排序，穩定。

複雜度對比總結

實際應用建議

• 小規模數據（n < 50）：插入排序常快於 O(n log n) 算法
• 近乎有序數據：插入排序或優化冒泡
• 交換成本極高：選擇排序（最少交換）
• 生產環境：優先使用 Arrays.sort()（雙軸快排/TimSort）