經典排序演算法 Java 實作全解析：氣泡、插入、選擇排序與效能比較

排序演算法是資料結構與演算法的基石。本文提供三種經典 O(n²) 排序——氣泡排序、插入排序、選擇排序的完整 Java 實作、步驟圖解、效能分析與優化技巧，並附上可直接執行的程式碼範例。

1. 氣泡排序

核心思想

重複掃描序列，比較相鄰元素，逆序則交換。每輪將最大元素「氣泡」至末端。優化：若某輪無交換，提前結束 (已有序)。

Java 實作 (含過程輸出)

public class BubbleSortDemo {
    // 優化版：雙向掃描 + 提前結束旗標
    public void bubbleSort(int[] numlist) {
        int temp;
        boolean swapped;
        // 外層：未排序區間縮減 [0, out]
        for (int out = numlist.length - 1; out > 0; out--) {
            swapped = true;
            // 內層：正向掃描將大值推後
            for (int in = 0; in < out; in++) {
                if (numlist[in] > numlist[in + 1]) {
                    temp = numlist[in];
                    numlist[in] = numlist[in + 1];
                    numlist[in + 1] = temp;
                    swapped = false;
                }
            }
            if (swapped) break; // 本輪無交換，已有序
            printArray(numlist); // 觀察每輪結果
        }
    }

    public void printArray(int[] arr) {
        for (int v : arr) System.out.print(v + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        BubbleSortDemo demo = new BubbleSortDemo();
        int[] num = {4, 11, 17, 6, 1, 2, 13, 15};
        System.out.println("原序列："); demo.printArray(num);
        System.out.println("每輪氣泡排序後："); demo.bubbleSort(num);
    }
}

效能特徵

• 時間複雜度：最好 O(n) (已有序)、平均/最差 O(n²)
• 空間複雜度：O(1) 原地排序
• 穩定性：穩定 (相等元素相對位置不變)
• 適用：小規模資料、近乎有序資料、教學示範

2. 插入排序

核心思想

將陣列分為「已排序區」與「未排序區」。每次從未排序區取首元素，在已排序區中從右向左比較位移，找到插入點。類似整理撲克牌。

Java 實作

public class InsertSortDemo {
    public void insertSort(int[] numlist) {
        int temp;
        // 外層：out 為未排序區首元素索引
        for (int out = 1; out < numlist.length; out++) {
            temp = numlist[out]; // 待插入值
            int in = out;
            // 內層：已排序區從右向左掃描，大於 temp 者右移
            while (in > 0 && temp < numlist[in - 1]) {
                numlist[in] = numlist[in - 1]; // 右移
                in--;
            }
            numlist[in] = temp; // 插入空位
        }
    }
    // printArray/main 同前
}

效能特徵

• 時間複雜度：最好 O(n) (已有序)、平均/最差 O(n²)
• 空間複雜度：O(1)
• 穩定性：穩定
• 優勢：資料移動次數少於氣泡排序，小規模/近乎有序資料最快，常作為快速排序小區間優化閾值。

3. 選擇排序

核心思想

每輪在未排序區尋找最小元素，與區首元素交換。不需相鄰比較交換，僅每輪 1 次交換。

Java 實作

public class SelectSortDemo {
    public void selectSort(int[] numlist) {
        int temp;
        for (int out = 0; out < numlist.length; out++) {
            int min = out; // 假設 out 為最小
            // 掃描未排序區尋找真正最小值索引
            for (int in = out + 1; in < numlist.length; in++) {
                if (numlist[in] < numlist[min]) min = in;
            }
            // 單次交換將最小值放至 out 位置
            temp = numlist[out];
            numlist[out] = numlist[min];
            numlist[min] = temp;
        }
    }
    // printArray/main 同前
}

效能特徵

• 時間複雜度：固定 O(n²) (無論輸入分佈)，無最好情況優化
• 空間複雜度：O(1)
• 穩定性：不穩定 (交換可能改變相等元素相對順序)
• 優勢：寫入操作最少 (僅 n 次交換)，適合寫入成本高的儲存介質 (如 EEPROM、Flash)。

三大排序綜合比較表

進階延伸：JDK 內建排序

實務開發請直接使用 Arrays.sort() (雙軸快速排序，基本型別) 或 Collections.sort() / List.sort() (TimSort，物件參考)，時間複雜度 O(n log n)、高度優化、穩定。僅在教學、嵌入式無標準庫、或特殊約束 (如寫入極昂貴) 時手寫 O(n²) 排序。

// 實務標準用法
int[] arr = {4, 11, 17, 6, 1, 2, 13, 15};
Arrays.sort(arr); // 原地排序，最快
System.out.println(Arrays.toString(arr)); // [1, 2, 4, 6, 11, 13, 15, 17]

總結

• 理解 O(n²) 排序機制是掌握進階演算法 (快排、合併排序、堆排序) 的基礎。
• 插入排序綜合表現最佳，常作為分治法遞歸基例優化。
• 選擇排序寫入最少，針對特殊硬體場景。
• 生產代碼永遠優先使用標準庫 Arrays/Collections.sort。