跳到主要內容
Jasonmel Online

演算法

同一個問題，不同的解題思路

主題 · 計數排序與基數排序

計數排序與基數排序

不比大小的排序：鍵的範圍有限時，直接數每個值出現幾次就能排好，突破比較排序 n log n 的下限。

做法

鍵只有 0 到 9：先數每個值出現幾次，把次數累加成「每個值最後一個該放在哪」，再從後往前把每個元素放進去。整個過程沒有比較過任何兩個數。

1/35
輸入（這一輪）
6
0
7
1
2
2
6
3
0
4
5
5
7
6
4
7
9
8
2
9
7
10
7
11
count[值]
0
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
0
9
輸出
0
1
2
3
4
5
6
7
8
9
10
11
正在讀的元素正在改的計數剛放進去
鍵的個數 n
12
計數格數 k + 1
10
操作次數
0
全部跑完
33

12 個鍵。每格下面的小數字是它原本的位置，用來看相同的鍵有沒有保持原來的順序。

亮起來的是這一步執行的程式碼
function countingSort(a: number[], k: number): number[] {
  const count = new Array(k + 1).fill(0);
  for (const v of a) count[v]++;
  for (let j = 1; j <= k; j++) {
    count[j] += count[j - 1];
  }
  const out = new Array(a.length);
  for (let i = a.length - 1; i >= 0; i--) {
    count[a[i]]--;
    out[count[a[i]]] = a[i];
  }
  return out;
}
 
function radixSort(a: number[]): number[] {
  const max = Math.max(0, ...a);
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    const count = new Array(10).fill(0);
    for (const v of a) count[Math.floor(v / exp) % 10]++;
    for (let d = 1; d < 10; d++) {
      count[d] += count[d - 1];
    }
    const out = new Array(a.length);
    for (let i = a.length - 1; i >= 0; i--) {
      const d = Math.floor(a[i] / exp) % 10;
      out[--count[d]] = a[i];
    }
    a = out;
  }
  return a;
}

模型假設與範圍

  • Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

  • 鍵是範圍不大的整數（年齡、考試分數、0–255 的像素亮度）：計數排序掃兩遍就排好。
  • 鍵是固定長度的數字或字串（郵遞區號、日期、IP 位址）：基數排序一位一位排，每一位都是一次計數排序。
  • 需要穩定排序：相同的鍵保持原來的先後順序，可以接在其他排序後面當第二個排序條件。

和其他主題的關係

延伸閱讀
排序

時間與空間複雜度（Big O）

操作平均最差
計數排序
k 是鍵的範圍；k 和 n 差不多時就是 O(n)
O(n + k)O(n + k)
基數排序
d 是位數、b 是基數（這裡是 10）
O(d·(n + b))O(d·(n + b))
任何比較排序的下限
只靠比大小，最差至少要這麼多次比較；不比較才能繞過
O(n log n)O(n log n)

空間：O(n + k)，一個計數陣列加一個輸出陣列，不是原地排序

Big O 實測：n 變大時步數怎麼長

數的是：操作或比較次數，鍵固定在 0–99

Big On = 1,000n = 10,000n = 100,000成長倍數：實測（理論）
計數排序O(n)2,09920,099200,099×95 (×100)
基數排序（2 輪）O(n)4,01840,018400,018×100 (×100)
合併排序（比較）O(n log n)8,692120,2311,532,268×176 (×167)

k 固定時，計數和基數排序的工作量跟著 n 成正比；合併排序每多十倍還要再多乘上 log n 長出來的那一點。

和其他做法比

計數排序：操作基數排序：操作（輪數）合併排序：比較
n = 1,000，鍵 0–992,0994,018 (2)8,692
n = 1,000，鍵 0–999,9991,001,99912,054 (6)8,703
n = 10,000，鍵 0–9920,09940,018 (2)120,252

同一組隨機鍵交給三種排序。計數排序的操作數是 2n + k：鍵的範圍到 999,999 時，它要 1,001,999 次操作，大部分花在一個幾乎全空的計數陣列上，反而比合併排序的 8,703 次比較慢得多；基數排序把同樣的鍵拆成 6 輪、每輪只有 10 格，就不受 k 影響。

真實世界裡的它

  • 影像處理的直方圖：0–255 的亮度值先數再處理，正是計數排序的前半段。
  • 早期的打孔卡分類機就是基數排序：一次依一欄把卡片分進 10 個槽，再依下一欄。
  • GPU 上的大量排序、字尾陣列的建構，常用基數排序。

取捨與陷阱

  • 鍵的範圍很大時反而很慢：範圍到一百萬，計數陣列就要一百萬格（看上面的比較表）。
  • 只適用於能變成小整數的鍵；浮點數或任意字串要先轉換。
  • 放回輸出時一定要從後往前：從前往後會讓相同的鍵反序，基數排序就會排錯。
  • 需要額外 O(n + k) 的記憶體，不是原地排序。

LeetCode 練習