Java 十大經典排序算法實作與效能基準測試完整指南

前言：為何仍需手寫排序？

雖然生產環境首選 Arrays.sort()（TimSort，混合歸並與插入），但理解經典排序算法是面試必考、演算法思維訓練的基石。本文提供 10 種排序的標準實作、優化版本、效能測試框架與實測數據，助你建立完整知識體系。

效能測試結果（陣列長度 20,000，平均 20 次，單位 ms）

核心結論

• 冒泡排序應丟進垃圾桶：唯一優勢是「最好理解」，實務零價值。
• 希爾排序令人驚艷：簡單優化即達 O(n log n) 量級，適合中小型陣列或近乎有序資料。
• 堆排序需宏觀思維：完全二叉樹性質保證最壞情況效能，嵌入式/即時系統首選。
• 快速排序是通用王者：隨機化樞紐或三數取中可避免最壞退化。

關鍵算法實作精要

快速排序（單樞紐雙向掃描，最易理解版本）

public static void quickSort(int[] a, int low, int high) {
    if (low >= high) return;
    int low0 = low, high0 = high;
    boolean forward = false;  // false: high 向左, true: low 向右
    while (low0 != high0) {
        if (a[low0] > a[high0]) {
            swap(a, low0, high0);
            forward = !forward;  // 交換後改變掃描方向
        }
        if (forward) low0++; else high0--;
    }
    // 遞迴處理左右分區
    quickSort(a, low, low0 - 1);
    quickSort(a, high0 + 1, high);
}

關鍵洞見：forward 標誌確保樞紐元素在交換後自動移動到正確分區邊界，避免額外交換邏輯。

希爾排序（優化版：合併子序列單層迴圈）

public static void shellSortAdvanced(int[] a) {
    for (int gap = a.length / 2; gap > 0; gap /= 2) {
        for (int j = gap; j < a.length; j++) {
            if (a[j] < a[j - gap]) {
                int tmp = a[j];
                int k = j - gap;
                while (k >= 0 && a[k] > tmp) {
                    a[k + gap] = a[k];
                    k -= gap;
                }
                a[k + gap] = tmp;
            }
        }
    }
}

步長選擇影響巨大：gap = gap/2 為最基礎序列，Sedgewick、Pratt、Ciura 序列可進一步提升 20-30% 效能。

歸並排序（遞迴分治，返回新陣列）

public static int[] mergeSort(int[] a) {
    if (a.length == 1) return a;
    int mid = a.length / 2;
    int[] left = mergeSort(Arrays.copyOfRange(a, 0, mid));
    int[] right = mergeSort(Arrays.copyOfRange(a, mid, a.length));
    return merge(left, right);
}

private static int[] merge(int[] a, int[] b) {
    int[] res = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length)
        res[k++] = (a[i] < b[j]) ? a[i++] : b[j++];
    while (i < a.length) res[k++] = a[i++];
    while (j < b.length) res[k++] = b[j++];
    return res;
}

堆排序（最大堆，原地排序）

public static void heapSort(int[] a) {
    // 建堆：從最後一個非葉節點向上調整
    for (int i = (a.length - 2) / 2; i >= 0; i--)
        maxHeapAdjust(a, i, a.length);
    // 排序：逐個取出堆頂，縮小堆範圍
    for (int i = a.length - 1; i > 0; i--) {
        swap(a, 0, i);
        maxHeapAdjust(a, 0, i);
    }
}

private static void maxHeapAdjust(int[] a, int i, int len) {
    int tmp = a[i];
    for (int j = 2 * i + 1; j < len; j = 2 * j + 1) {
        if (j + 1 < len && a[j + 1] > a[j]) j++;  // 取較大子節點
        if (a[j] < tmp) break;  // 找到位置
        a[i] = a[j];  // 子節點上移
        i = j;
    }
    a[i] = tmp;
}

測試框架核心代碼（反射動態調用）

public static void performanceTest(int len) throws Exception {
    int[] a = new int[len];
    int times = 20;
    String[] methods = {"bubbleSort", "quickSort", "mergeSort", ...};
    for (String m : methods) {
        Method method = SortUtil.class.getDeclaredMethod(m, int[].class);
        long total = 0;
        for (int t = 0; t < times; t++) {
            randomize(a);
            long start = System.nanoTime();
            method.invoke(null, a);
            total += System.nanoTime() - start;
        }
        System.out.printf("%s: %.2f ms%n", m, total / times / 1e6);
    }
}

面試高頻考點速查

總結

掌握排序不只是背誦代碼，而是理解：資料分布特性 → 選擇最適算法 → 针對性優化。實務中：

• 小陣列（<50）：插入排序
• 中等陣列、近乎有序：希爾排序 / TimSort
• 大陣列、通用：快速排序（隨機樞紐）
• 需穩定、最壞情況保證：歸並 / 堆排序
• 整數、已知範圍：計數/基數排序 O(n)

本文所有代碼已整理為可直接執行的 SortUtil 類，歡迎複製實驗、擴充測試。