進階排序：O(n log n) 排序演算法#

歸併排序與快速排序是處理大規模資料的主力演算法，兩者都運用分治思想，但策略截然不同。

分治思想#

將大問題分解為小問題，解決小問題後合併結果。

flowchart TB
    subgraph 歸併排序["歸併排序：由下而上"]
        direction TB
        M1[分解陣列] --> M2[遞迴排序左半]
        M1 --> M3[遞迴排序右半]
        M2 --> M4[合併結果]
        M3 --> M4
    end

    subgraph 快速排序["快速排序：由上而下"]
        direction TB
        Q1[選擇 Pivot] --> Q2[分區操作]
        Q2 --> Q3[遞迴排序左區]
        Q2 --> Q4[遞迴排序右區]
    end

    style M4 fill:#e8f5e9
    style Q2 fill:#fff3e0
T(n) = 2*T(n/2) + O(n)  =>  T(n) = O(n log n)

歸併排序 (Merge Sort)#

由下而上：先遞迴處理子問題，再合併結果。

核心流程#

  1. 將陣列從中間分成兩半
  2. 對左右兩半分別遞迴排序
  3. 合併兩個有序陣列
特性說明
時間複雜度穩定 O(n log n)，不受輸入影響
空間複雜度O(n)，需要臨時陣列
穩定性穩定
歸併排序程式碼
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= 保證穩定性
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

歸併排序的空間複雜度是 O(n) 而非 O(n log n)。雖然遞迴層數是 log n，但同一時間只有一個函式在執行，臨時空間會被釋放重用。

快速排序 (Quick Sort)#

由上而下：先分區，再遞迴處理子問題。

核心流程#

  1. 選擇一個 pivot（分區點）
  2. 將小於 pivot 的放左邊，大於 pivot 的放右邊
  3. 對左右兩部分遞迴排序
特性說明
時間複雜度平均 O(n log n)，最壞 O(n²)
空間複雜度O(log n)，原地排序
穩定性不穩定
快速排序程式碼（原地分區）
def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)
        quick_sort(arr, pivot_idx + 1, high)
    return arr

def partition(arr, low, high):
    pivot = arr[high]  # 選最後一個元素作為 pivot
    i = low
    for j in range(low, high):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[high] = arr[high], arr[i]
    return i

快排優化策略#

問題：最壞情況 O(n²)#

當資料已有序且每次選最後一個元素作為 pivot 時，分區極度不均衡。

解決方案#

  1. 三數取中法：取首、中、尾三個數的中位數作為 pivot
  2. 隨機法：隨機選擇 pivot，降低最壞情況發生的概率
  3. 避免遞迴過深：設定遞迴深度閾值，或使用堆上的堆疊模擬遞迴

快排 vs 歸併

比較項目歸併排序快速排序
時間穩定性穩定 O(n log n)平均 O(n log n)，可能退化
空間複雜度O(n)O(log n)
實際應用較少（記憶體消耗大）較多（原地、常數項小）

經典應用：O(n) 查找第 K 大元素#

利用快排的分區思想，可以在 O(n) 時間內找到無序陣列中的第 K 大元素。

第 K 大元素程式碼
def find_kth_largest(arr, k):
    def partition(low, high):
        pivot = arr[high]
        i = low
        for j in range(low, high):
            if arr[j] >= pivot:  # 降序分區
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
        arr[i], arr[high] = arr[high], arr[i]
        return i

    low, high = 0, len(arr) - 1
    while low <= high:
        pivot_idx = partition(low, high)
        if pivot_idx == k - 1:
            return arr[pivot_idx]
        elif pivot_idx < k - 1:
            low = pivot_idx + 1
        else:
            high = pivot_idx - 1
    return -1

為何是 O(n)？每次只需處理一半：n + n/2 + n/4 + … = 2n = O(n)

工業級排序函式實作（以 C 語言 qsort 為例）#

  1. 小資料量：使用歸併排序（空間換時間可接受）
  2. 大資料量：使用快速排序
  3. 分區點選擇：三數取中法
  4. 遞迴優化：堆上模擬堆疊，避免堆疊溢出
  5. 小區間優化：元素 <= 4 時切換為插入排序
Backward 基礎排序 線性排序 Forward