基數排序

提醒

本頁面要介紹的不是 計數排序。

本頁面將簡要介紹基數排序。

定義

基數排序（英語：Radix sort）是一種非比較型的排序算法，最早用於解決卡片排序的問題。基數排序將待排序的元素拆分為 \(k\) 個關鍵字，逐一對各個關鍵字排序後完成對所有元素的排序。

如果是從第 \(1\) 關鍵字到第 \(k\) 關鍵字順序進行比較，則該基數排序稱為 MSD（Most Significant Digit first）基數排序；

如果是從第 \(k\) 關鍵字到第 \(1\) 關鍵字順序進行比較，則該基數排序稱為 LSD（Least Significant Digit first）基數排序。

k - 關鍵字元素的比較

下面用 \(a_i\) 表示元素 \(a\) 的第 \(i\) 關鍵字。

假如元素有 \(k\) 個關鍵字，對於兩個元素 \(a\) 和 \(b\)，默認的比較方法是：

比較兩個元素的第 \(1\) 關鍵字 \(a_1\) 和 \(b_1\)，如果 \(a_1 < b_1\) 則 \(a < b\)，如果 \(a_1 > b_1\) 則 \(a > b\)，如果 \(a_1 = b_1\) 則進行下一步；
比較兩個元素的第 \(2\) 關鍵字 \(a_2\) 和 \(b_2\)，如果 \(a_2 < b_2\) 則 \(a < b\)，如果 \(a_2 > b_2\) 則 \(a > b\)，如果 \(a_2 = b_2\) 則進行下一步；
……
比較兩個元素的第 \(k\) 關鍵字 \(a_k\) 和 \(b_k\)，如果 \(a_k < b_k\) 則 \(a < b\)，如果 \(a_k > b_k\) 則 \(a > b\)，如果 \(a_k = b_k\) 則 \(a = b\)。

例子：

如果對自然數進行比較，將自然數按個位對齊後往高位補齊 \(0\)，則一個數字從左往右數第 \(i\) 位數就可以作為第 \(i\) 關鍵字；
如果對字符串基於字典序進行比較，一個字符串從左往右數第 \(i\) 個字符就可以作為第 \(i\) 關鍵字；
C++ 自帶的 std::pair 與 std::tuple 的默認比較方法與上述的相同。

MSD 基數排序

基於 k - 關鍵字元素的比較方法，可以想到：先比較所有元素的第 \(1\) 關鍵字，就可以確定出各元素大致的大小關係；然後對 具有相同第 \(1\) 關鍵字的元素，再比較它們的第 \(2\) 關鍵字……以此類推。

由於是從第 \(1\) 關鍵字到第 \(k\) 關鍵字順序進行比較，由上述思想導出的排序算法稱為 MSD（Most Significant Digit first）基數排序。

算法流程

將待排序的元素拆分為 \(k\) 個關鍵字，先對第 \(1\) 關鍵字進行穩定排序，然後對於每組 具有相同關鍵字的元素 再對第 \(2\) 關鍵字進行穩定排序（遞歸執行）……最後對於每組 具有相同關鍵字的元素 再對第 \(k\) 關鍵字進行穩定排序。

一般而言，我們默認基數排序是穩定的，所以在 MSD 基數排序中，我們也僅僅考慮藉助 穩定算法（通常使用計數排序）完成內層對關鍵字的排序。

正確性參考上文 k - 關鍵字元素的比較。

參考代碼

對自然數排序

下面是使用迭代式 MSD 基數排序對 unsigned int 範圍內元素進行排序的 C++ 參考代碼，可調整 \(W\) 和 \(\log_2 W\) 的值（建議將 \(\log_2 W\) 設為 \(2^k\) 以便位運算優化）。

#include <algorithm>
#include <stack>
#include <tuple>
#include <vector>

using std::copy;  // from <algorithm>
using std::make_tuple;
using std::stack;
using std::tie;
using std::tuple;
using std::vector;

typedef unsigned int u32;
typedef unsigned int* u32ptr;

void MSD_radix_sort(u32ptr first, u32ptr last) {
  const size_t maxW = 0x100000000llu;
  const u32 maxlogW = 32;  // = log_2 W

  const u32 W = 256;  // 計數排序的值域
  const u32 logW = 8;
  const u32 mask = W - 1;  // 用位運算替代取模，詳見下面的 key 函數

  u32ptr tmp =
      (u32ptr)calloc(last - first, sizeof(u32));  // 計數排序用的輸出空間

  typedef tuple<u32ptr, u32ptr, u32> node;
  stack<node, vector<node>> s;
  s.push(make_tuple(first, last, maxlogW - logW));

  while (!s.empty()) {
    u32ptr begin, end;
    size_t shift, length;

    tie(begin, end, shift) = s.top();
    length = end - begin;
    s.pop();

    if (begin + 1 >= end) continue;  // elements <= 1

    // 計數排序
    u32 cnt[W] = {};
    auto key = [](const u32 x, const u32 shift) { return (x >> shift) & mask; };

    for (u32ptr it = begin; it != end; ++it) ++cnt[key(*it, shift)];
    for (u32 value = 1; value < W; ++value) cnt[value] += cnt[value - 1];

    // 求完前綴和後，計算相同關鍵字的元素範圍
    if (shift >= logW) {
      s.push(make_tuple(begin, begin + cnt[0], shift - logW));
      for (u32 value = 1; value < W; ++value)
        s.push(make_tuple(begin + cnt[value - 1], begin + cnt[value],
                          shift - logW));
    }

    u32ptr it = end;
    do {
      --it;
      --cnt[key(*it, shift)];
      tmp[cnt[key(*it, shift)]] = *it;
    } while (it != begin);

    copy(tmp, tmp + length, begin);
  }
}

對字符串排序

下面是使用迭代式 MSD 基數排序對空終止字節字符串基於字典序進行排序的 C++ 參考代碼：

#include <algorithm>
#include <stack>
#include <tuple>
#include <vector>

using std::copy;  // from <algorithm>
using std::make_tuple;
using std::stack;
using std::tie;
using std::tuple;
using std::vector;

typedef char* NTBS;  // 空終止字節字符串
typedef NTBS* NTBSptr;

void MSD_radix_sort(NTBSptr first, NTBSptr last) {
  const size_t W = 128;
  const size_t logW = 7;
  const size_t mask = W - 1;

  NTBSptr tmp = (NTBSptr)calloc(last - first, sizeof(NTBS));

  typedef tuple<NTBSptr, NTBSptr, size_t> node;
  stack<node, vector<node>> s;
  s.push(make_tuple(first, last, 0));

  while (!s.empty()) {
    NTBSptr begin, end;
    size_t index, length;

    tie(begin, end, index) = s.top();
    length = end - begin;
    s.pop();

    if (begin + 1 >= end) continue;  // elements <= 1

    // 計數排序
    size_t cnt[W] = {};
    auto key = [](const NTBS str, const size_t index) { return str[index]; };

    for (NTBSptr it = begin; it != end; ++it) ++cnt[key(*it, index)];
    for (char ch = 1; value < W; ++value) cnt[ch] += cnt[ch - 1];

    // 求完前綴和後，計算相同關鍵字的元素範圍
    // 對於 NTBS，如果此刻末尾的字符是 \0 則説明這兩個字符串相等，不必繼續迭代
    for (char ch = 1; ch < W; ++ch)
      s.push(make_tuple(begin + cnt[ch - 1], begin + cnt[ch], index + 1));

    NTBSptr it = end;
    do {
      --it;
      --cnt[key(*it, index)];
      tmp[cnt[key(*it, index)]] = *it;
    } while (it != begin);

    copy(tmp, tmp + length, begin);
  }

  free(tmp);
}

由於兩個字符串的比較很容易衝上 \(O(n)\) 的線性複雜度，因此在字符串排序這件事情上，MSD 基數排序比大多數基於比較的排序算法在時間複雜度和實際用時上都更加優秀。

與桶排序的關係

前置知識：桶排序

桶排序需要其它的排序算法來完成對每個桶內部元素的排序。但實際上，完全可以對每個桶繼續執行桶排序，直至某一步桶的元素數量 \(\le 1\)。

因此 MSD 基數排序的另一種理解方式是：使用桶排序實現的桶排序。

也因此，可以提出 MSD 基數排序在時間常數上的一種優化方法：假如到某一步桶的元素數量 \(\le B\)（\(B\) 是自己選的常數），則直接執行插入排序然後返回，降低遞歸次數。

LSD 基數排序

MSD 基數排序從第 \(1\) 關鍵字到第 \(k\) 關鍵字順序進行比較，為此需要藉助遞歸或迭代來實現，時間常數還是較大，而且在比較自然數上還是略顯不便。

而將遞歸的操作反過來：從第 \(k\) 關鍵字到第 \(1\) 關鍵字順序進行比較，就可以得到 LSD（Least Significant Digit first）基數排序，不使用遞歸就可以完成的排序算法。

算法流程

將待排序的元素拆分為 \(k\) 個關鍵字，然後先對 所有元素 的第 \(k\) 關鍵字進行穩定排序，再對 所有元素 的第 \(k-1\) 關鍵字進行穩定排序，再對 所有元素 的第 \(k-2\) 關鍵字進行穩定排序……最後對 所有元素 的第 \(1\) 關鍵字進行穩定排序，這樣就完成了對整個待排序序列的穩定排序。

一個 LSD 基數排序全流程的例子

LSD 基數排序也需要藉助一種 穩定算法 完成內層對關鍵字的排序。同樣的，通常使用計數排序來完成。

LSD 基數排序的正確性可以參考《算法導論（第三版）》第 8.3-3 題的解法或參考下面的解釋：

正確性

回顧一下 k - 關鍵字元素的比較方法，

假如想通過 \(a_1\) 和 \(b_1\) 就比較出兩個元素 \(a\) 和 \(b\) 的大小，則需要提前知道通過比較 \(a_2\) 和 \(b_2\) 得到的結論，以便於應對 \(a_1 = b_1\) 的情況；
而想通過 \(a_2\) 和 \(b_2\) 就比較出兩個元素 \(a\) 和 \(b\) 的大小，則需要提前知道通過比較 \(a_3\) 和 \(b_3\) 得到的結論，以便於應對 \(a_2 = b_2\) 的情況；
……
而想通過 \(a_{k-1}\) 和 \(b_{k-1}\) 就比較出兩個元素 \(a\) 和 \(b\) 的大小，則需要提前知道通過比較 \(a_k\) 和 \(b_k\) 得到的結論，以便於應對 \(a_{k-1} = b_{k-1}\) 的情況；
\(a_k\) 和 \(b_k\) 可以直接比較。

現在，將順序反過來：

\(a_k\) 和 \(b_k\) 可以直接比較；
而知道通過比較 \(a_k\) 和 \(b_k\) 得到的結論後，就可以得到比較 \(a_{k-1}\) 和 \(b_{k-1}\) 的結論；
……
而知道通過比較 \(a_2\) 和 \(b_2\) 得到的結論後，就可以得到比較 \(a_1\) 和 \(b_1\) 的結論；
而知道通過比較 \(a_1\) 和 \(b_1\) 得到的結論後，就最終得到了比較 \(a\) 和 \(b\) 的結論。

在這個過程中，對每個關鍵字邊比較邊重排元素的順序，就得到了 LSD 基數排序。

偽代碼

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements, where each element has }k\text{ keys.}\\ 2 & \textbf{Output. } \text{Array }A\text{ will be sorted in nondecreasing order stably.} \\ 3 & \textbf{Method. } \\ 4 & \textbf{for }i\gets k\textbf{ down to }1\\ 5 & \qquad\text{sort }A\text{ into nondecreasing order by the }i\text{-th key stably} \end{array} \]

參考代碼

下面是使用 LSD 基數排序實現的對 k - 關鍵字元素的排序。

const int N = 100010;
const int W = 100010;
const int K = 100;

int n, w[K], k, cnt[W];

struct Element {
  int key[K];

  bool operator<(const Element& y) const {
    // 兩個元素的比較流程
    for (int i = 1; i <= k; ++i) {
      if (key[i] == y.key[i]) continue;
      return key[i] < y.key[i];
    }
    return false;
  }
} a[N], b[N];

void counting_sort(int p) {
  memset(cnt, 0, sizeof(cnt));
  for (int i = 1; i <= n; ++i) ++cnt[a[i].key[p]];
  for (int i = 1; i <= w[p]; ++i) cnt[i] += cnt[i - 1];
  // 為保證排序的穩定性，此處循環i應從n到1
  // 即當兩元素關鍵字的值相同時，原先排在後面的元素在排序後仍應排在後面
  for (int i = n; i >= 1; --i) b[cnt[a[i].key[p]]--] = a[i];
  memcpy(a, b, sizeof(a));
}

void radix_sort() {
  for (int i = k; i >= 1; --i) {
    // 藉助計數排序完成對關鍵字的排序
    counting_sort(i);
  }
}

實際上並非必須從後往前枚舉才是穩定排序，只需對 cnt 數組進行等價於 std::exclusive_scan 的操作即可。

例題洛谷 P1177【模板】快速排序

給出 \(n\) 個正整數，從小到大輸出。

#include <algorithm>
#include <iostream>
#include <utility>

void radix_sort(int n, int a[]) {
  int *b = new int[n];  // 臨時空間
  int *cnt = new int[1 << 8];
  int mask = (1 << 8) - 1;
  int *x = a, *y = b;
  for (int i = 0; i < 32; i += 8) {
    for (int j = 0; j != (1 << 8); ++j) cnt[j] = 0;
    for (int j = 0; j != n; ++j) ++cnt[x[j] >> i & mask];
    for (int sum = 0, j = 0; j != (1 << 8); ++j) {
      // 等價於 std::exclusive_scan(cnt, cnt + (1 << 8), cnt, 0);
      sum += cnt[j], cnt[j] = sum - cnt[j];
    }
    for (int j = 0; j != n; ++j) y[cnt[x[j] >> i & mask]++] = x[j];
    std::swap(x, y);
  }
  delete[] cnt;
  delete[] b;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int n;
  std::cin >> n;
  int *a = new int[n];
  for (int i = 0; i < n; ++i) std::cin >> a[i];
  radix_sort(n, a);
  for (int i = 0; i < n; ++i) std::cout << a[i] << ' ';
  delete[] a;
  return 0;
}

性質

穩定性

如果對內層關鍵字的排序是穩定的，則 MSD 基數排序和 LSD 基數排序都是穩定的排序算法。

時間複雜度

通常而言，基數排序比基於比較的排序算法（比如快速排序）要快。但由於需要額外的內存空間，因此當內存空間稀缺時，原地置換算法（比如快速排序）或許是個更好的選擇。¹

一般來説，如果每個關鍵字的值域都不大，就可以使用計數排序作為內層排序，此時的複雜度為 \(O(kn+\sum\limits_{i=1}^k w_i)\)，其中 \(w_i\) 為第 \(i\) 關鍵字的值域大小。如果關鍵字值域很大，就可以直接使用基於比較的 \(O(nk\log n)\) 排序而無需使用基數排序了。

空間複雜度

MSD 基數排序和 LSD 基數排序的空間複雜度都為 \(O(k+n)\)。

參考資料與註釋

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.Introduction to Algorithms(3^rd ed.). MIT Press and McGraw-Hill, 2009. ISBN 978-0-262-03384-8. "8.3 Radix sort", pp. 199. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用