Java 陣列排序演算法實作：快速排序、氣泡排序、選擇排序完整教學

前言

排序演算法是資料結構基石。本文以 Java 實作三種經典排序：快速排序 (分治、平均 O(n log n))、氣泡排序 (教學用、O(n²))、選擇排序 (原地、O(n²))，並對比 Arrays.sort() (Dual-Pivot QuickSort + TimSort) 的工業級實作，幫助理解原理與效能差距。

1. 快速排序

核心思想

1. 選擇基準值 (pivot)。
2. 分區：小於 pivot 置左，大於 pivot 置右。
3. 遞迴處理左右子陣列。

標準實作 (Hoare 分區)

public class QuickSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }

    private static int partition(int[] arr, int left, int right) {
        // 隨機基準值避免最壞情況
        int rand = left + new Random().nextInt(right - left + 1);
        swap(arr, rand, right);
        int pivot = arr[right];
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, right);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

效能特性

• 平均 O(n log n)，最壞 O(n²) (已排序陣列 + 固定基準值)。
• 原地排序，空間複雜度 O(log n) 遞迴堆疊。
• 不穩定 (相等元素相對位置可能改變)。

2. 氣泡排序

核心思想

重複遍歷陣列，相鄰元素比較交換，大值像氣泡浮到右端。

優化實作 (雙向氣泡 / Cocktail Shaker)

public class BubbleSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        boolean swapped;
        int start = 0, end = arr.length - 1;
        do {
            swapped = false;
            // 正向：大值右移
            for (int i = start; i < end; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                    swapped = true;
                }
            }
            if (!swapped) break;
            end--;
            // 反向：小值左移
            for (int i = end; i > start; i--) {
                if (arr[i] < arr[i - 1]) {
                    swap(arr, i, i - 1);
                    swapped = true;
                }
            }
            start++;
        } while (swapped);
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

效能特性

• O(n²) 時間，O(1) 空間。
• 穩定 (不交換相等元素)。
• 近乎有序資料可提早結束 (最佳 O(n))。
• 僅適合教學或極小資料集 (< 50)。

3. 選擇排序

核心思想

每輪從未排序區選最小值，換到已排序區末尾。

標準實作

public class SelectionSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        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;
            }
            if (minIdx != i) swap(arr, i, minIdx);
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

效能特性

• O(n²) 時間，O(1) 空間。
• 不穩定 (交換可能改變相等元素順序)。
• 交換次數最少 (最多 n-1 次)，適合寫入成本高的儲體 (如 EEPROM)。

4. Arrays.sort() 工業級實作 (JDK 17)

關鍵優化：小陣列 (< 47) 改用插入排序；偵測有序段落 (run) 直接合併；雙基準值減少遞迴深度。

效能實測 (100萬亂數 int[])

何時使用哪種排序？

1. 生產程式碼：永遠用 Arrays.sort() / Collections.sort() / Stream.sorted()。
2. 面試手寫：快速排序 (含隨機基準值)、合併排序 (穩定、外部排序基礎)。
3. 教學示範：氣泡/選擇/插入排序，觀察邏輯流程。
4. 特殊硬體限制：寫入極貴 → 選擇排序；近乎有序 → 插入/氣泡排序；嵌入式無遞迴 → 迭代式快速/堆積排序。

常見面試追問

• 快速排序最壞情況如何避免？ → 隨機基準值 / 三數取中 / IntroSort (超深度改堆積排序)。
• 為何物件陣列用 TimSort？ → 穩定性保證、利用現有有序段落 (run) 加速。
• 如何實作穩定的快速排序？ → 額外空間 O(n) 複製分區、或改用合併排序。