面試必備：十大經典排序算法全景解析與 Java 實現

前言

排序算法是面試高頻考點，也是算法基石。本文系統梳理 10 大排序算法的核心思想、複雜度、穩定性、適用場景，並提供可直接運行的 Java 實現代碼，助你面試手到擒來。

算法總覽表

核心算法深度解析

1. 快速排序 —— 面試最愛

單邊循環法優化版（避免交換開銷）：

public static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= pivot) right--;
        arr[left] = arr[right];           // 直接覆蓋，省去 swap
        while (left < right && arr[left] <= pivot) left++;
        arr[right] = arr[left];
    }
    arr[left] = pivot;                    // 基準值歸位
    return left;
}

關鍵點：基準值選擇影響性能，可用「三數取中」或隨機化避免最壞情況。

2. 歸並排序 —— 穩定 O(n log n) 基石

public static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right)
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    System.arraycopy(temp, 0, arr, left, temp.length);
}

3. 堆排序 —— 原地 O(n log n) 唯一選擇

// 篩選調整：從 start 向下維護大頂堆
public static void heapAdjust(int[] arr, int start, int end) {
    int temp = arr[start];
    for (int i = 2*start+1; i <= end; i *= 2) {
        if (i < end && arr[i] < arr[i+1]) i++;  // 取較大子節點
        if (temp >= arr[i]) break;              // 已滿足堆性質
        arr[start] = arr[i];                    // 子節點上移
        start = i;
    }
    arr[start] = temp;
}

4. 線性排序三劍客

• 計數排序：適用小範圍整數，count[val]++ 統計頻次
• 桶排序：映射函數 f(k)=k/10 均勻分布，桶內快排
• 基數排序：LSD 從個位到最高位，穩定排序鍵

面試高頻追問

1. 為什麼快排平均 O(n log n) 卻不穩定？ 交換操作可能改變相等元素相對順序
2. 歸並 vs 快排如何選？ 需穩定/外部排序選歸並；內存敏感/平均快選快排
3. 比較排序下限證明：決策樹葉子 ≥ n!，高度 ≥ log(n!) = Ω(n log n)
4. 近乎有序數組用什麼？ 插入排序 O(n)，或希爾/快排切換閾值

選型決策樹

數據量小 (n < 50)        → 插入排序
需穩定 + O(n log n)      → 歸並排序
一般內部排序             → 快速排序 (隨機化基準)
嚴格 O(n log n) + 原地   → 堆排序
整數小範圍               → 計數排序
浮點數/大範圍均勻分布    → 桶排序
固定位數整數/字符串      → 基數排序

總結

沒有完美的排序，只有最適合場景的排序。面試重點：

• 信手拈來寫出快排分區與歸並合併核心代碼
• 清晰對比時空複雜度、穩定性、適用場景
• 理解比較排序下限證明與非比較排序突破條件