線性排序：O(n) 排序演算法#

線性排序能達到 O(n) 時間複雜度，關鍵在於不基於比較。但它們對資料有嚴格要求，適用場景較窄。

線性排序的核心：利用資料特徵，用空間換時間，避免元素間的比較操作。

桶排序 (Bucket Sort)#

將資料分到若干個有序的「桶」中，桶內排序後依序取出。

適用場景#

• 資料可以均勻分布到各個桶
• 外部排序（資料無法全部載入記憶體）

時間複雜度分析#

• n 個資料分到 m 個桶，每桶 k = n/m 個元素
• 桶內快排：O(k log k)
• 總複雜度：O(m _ k _ log k) = O(n * log(n/m))
• 當 m 接近 n 時，趨近 O(n)

桶排序的效能取決於資料分布的均勻程度。極端情況下（資料全部落入一個桶），會退化為 O(n log n)。

計數排序 (Counting Sort)#

桶排序的特例：當資料範圍不大時，每個值對應一個桶。

適用場景#

• 資料範圍 k 相對較小（k 不遠大於 n）
• 非負整數（或可轉換為非負整數）

演算法流程#

1. 建立計數陣列 C[0…k]，統計每個值的出現次數
2. 對 C 做累加：C[i] 表示 <= i 的元素個數
3. 從後往前走訪原陣列，將元素放到正確位置

def counting_sort(arr):
    if not arr:
        return arr

    max_val = max(arr)
    count = [0] * (max_val + 1)

    # 統計每個值的出現次數
    for num in arr:
        count[num] += 1

    # 累加計數
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # 從後往前走訪，保證穩定性
    result = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        idx = count[arr[i]] - 1
        result[idx] = arr[i]
        count[arr[i]] -= 1

    return result

經典應用：給 100 萬用戶按年齡排序

年齡範圍 1-120，建立 120 個桶，走訪一次即可完成排序。

基數排序 (Radix Sort)#

從最低位到最高位，依次對每一位進行穩定排序。

適用場景#

• 資料可以分割出「位」進行比較
• 位之間有遞進關係（高位相同才比較低位）
• 每位的取值範圍不大

演算法流程#

1. 對最低位（最後一位）排序
2. 對次低位排序
3. …重複直到最高位
4. 必須使用穩定排序（通常是計數排序）

基數排序每一位的排序必須是穩定的，否則低位的排序結果會被打亂。

三種線性排序的比較#

思考題#

如何將 D, a, F, B, c, A, z 排序為小寫在前、大寫在後，但內部不需有序？

這不需要排序演算法！使用快排的分區思想：

1. 設一個指標指向「已處理小寫字母」的末尾
2. 走訪陣列，遇到小寫字母就與指標位置交換並移動指標

時間複雜度 O(n)，空間複雜度 O(1)。