隨機化快速排序

import random

def randomized_quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return randomized_quicksort(left) + mid + randomized_quicksort(right)

def randomized_quickselect(arr, k):
    """找到第 k 小的元素 (0-indexed)"""
    if len(arr) == 1:
        return arr[0]
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    if k < len(left):
        return randomized_quickselect(left, k)
    elif k < len(left) + len(mid):
        return pivot
    else:
        return randomized_quickselect(right, k - len(left) - len(mid))

# 比較：固定 pivot vs 隨機 pivot
import time
for n in [1000, 10000]:
    arr = list(range(n))
    random.shuffle(arr)
    start = time.time()
    randomized_quicksort(arr[:])
    t1 = time.time() - start
    print(f"n={n}: 隨機 pivot = {t1:.4f}s")

深入分析：為何隨機 pivot 有效？

固定 pivot 的最壞情況

固定 pivot（如選第一個元素）在已排序或反排序輸入上會產生：

每次分割：1 個 pivot + n-1 個元素在一邊
遞迴深度：O(n) → 總時間 O(n²)

隨機 pivot 的期望分析

隨機 pivot 的期望時間為 O(n log n)，原因：

隨機選 pivot = 均勻隨機分割
期望上 pivot 至少有 25% 機率落在中間 50%
好的分割讓問題規模指數級下降
期望深度 O(log n)，每層 O(n) → 總和 O(n log n)

Quickselect 的期望時間

# 驗證線性期望
def expected_time_quickselect(n, trials=100):
    total_time = 0
    for _ in range(trials):
        arr = list(range(n))
        random.shuffle(arr)
        k = random.randint(0, n-1)
        start = time.time()
        randomized_quickselect(arr, k)
        total_time += time.time() - start
    return total_time / trials

for n in [100, 1000, 10000, 100000]:
    t = expected_time_quickselect(n, trials=50)
    print(f"n={n:6d}: 期望時間={t:.6f}s, T/n={t/n:.8f}")
# T/n 趨近常數 → 證明期望 O(n)

關鍵要點

✅ Randomized Quicksort 期望時間 O(n log n)，無最壞情況
✅ Randomized Quickselect 期望時間 O(n)
✅ 隨機化 = 消除對手攻擊（adversarial input）
✅ 隨機 pivot 的期望分析依賴「線性期望」性質
✅ Las Vegas 演算法允許無限壞的運氣（機率極低）

常見錯誤

程式碼範例

隨機化快速排序為什麼這麼重要？

你可能覺得快速排序已經是老掉牙的題目了，但加入「隨機化」這個關鍵元素後，它展現了幾個非常重要的概念：

為什麼需要隨機化？

傳統的 QuickSort 選擇固定 pivot（例如第一個元素）會導致 Worst Case O(n²)——當輸入已經是排序好的陣列時。這不是理論上的邊緣案例，而是真實世界中 API 回傳的資料常常就是已經排序好的！

隨機選 pivot 將 Worst Case 的發生機率降到幾乎為零。任何輸入陣列，隨機化 QuickSort 的期望時間都是 O(n log n)。

平均情況 vs 最壞情況

| 特性 | 傳統 QuickSort | 隨機化 QuickSort | |:----|:-------------|:----------------| | Worst Case | O(n²) — 已排序陣列 | O(n²) — 機率趨近於 0 | | Average Case | O(n log n) | O(n log n) | | 實作難度 | 簡單 | 簡單（多一行 random） | | 實戰選擇 | ❌ 不安全 | ✅ 業界標準 |

應用在真實問題

資料庫排序：PostgreSQL 的排序演算法使用隨機化 QuickSort
即時資料處理：串流資料的 Top-K 選擇
推薦系統：對分數進行排名選取

下一章預告：Monte Carlo 方法

QuickSort 是 Las Vegas 類型——保證正確但時間隨機。下一章的 Monte Carlo 方法是另一種極端——時間固定但答案可能錯誤。你會學到如何在科學計算和機器學習中利用這種「近似」策略。