基数排序

提醒

本页面要介绍的不是 计数排序。

本页面将简要介绍基数排序。

定义

基数排序（英语：Radix sort）是一种非比较型的排序算法，最早用于解决卡片排序的问题。基数排序将待排序的元素拆分为个关键字，逐一对各个关键字排序后完成对所有元素的排序。

如果是从第关键字到第关键字顺序进行比较，则该基数排序称为 MSD（Most Significant Digit first）基数排序；

如果是从第关键字到第关键字顺序进行比较，则该基数排序称为 LSD（Least Significant Digit first）基数排序。

k - 关键字元素的比较

下面用表示元素的第关键字。

假如元素有个关键字，对于两个元素和，默认的比较方法是：

比较两个元素的第关键字和，如果则，如果则，如果则进行下一步；
比较两个元素的第关键字和，如果则，如果则，如果则进行下一步；
……
比较两个元素的第关键字和，如果则，如果则，如果则。

例子：

如果对自然数进行比较，将自然数按个位对齐后往高位补齐，则一个数字从左往右数第位数就可以作为第关键字；
如果对字符串基于字典序进行比较，一个字符串从左往右数第个字符就可以作为第关键字；
C++ 自带的 std::pair 与 std::tuple 的默认比较方法与上述的相同。

MSD 基数排序

基于 k - 关键字元素的比较方法，可以想到：先比较所有元素的第关键字，就可以确定出各元素大致的大小关系；然后对 具有相同第关键字的元素，再比较它们的第关键字……以此类推。

由于是从第关键字到第关键字顺序进行比较，由上述思想导出的排序算法称为 MSD（Most Significant Digit first）基数排序。

算法流程

将待排序的元素拆分为个关键字，先对第关键字进行稳定排序，然后对于每组 具有相同关键字的元素 再对第关键字进行稳定排序（递归执行）……最后对于每组 具有相同关键字的元素 再对第关键字进行稳定排序。

MSD 基数排序需要借助一种 稳定算法 完成内层对关键字的排序，通常使用计数排序来完成。

正确性参考上文 k - 关键字元素的比较。

参考代码

下面是使用 MSD 基数排序对字符串基于字典序进行排序的 C++ 参考代码：

#include <queue>
#include <string>

using std::queue;
using std::string;

// 计数排序的值域
const size_t MAXBUCKET = 128;

// 注意一定要将这两套容器放在执行递归操作的函数外边，否则很有可能 MLE / RE
queue<string> bucket[MAXBUCKET];  // 存储具有相同关键字的元素，注意使用 queue
                                  // 这种 FIFO 型数据结构才能使排序稳定
string *borders[MAXBUCKET + 1] =
    {};  // 具有相同关键字元素的范围边界，注意是 [L, R) 形式的

// [first, last) 里的元素是每个字符串
// offset 表示访问每个字符串的第 offset 个字符，即第 offset 关键字
void MSD_radix_sort(string *first, string *last, size_t offset = 0) {
  // 如果只剩一个字符串，直接返回
  if (last - first == 1) return;

  // 使用基于 queue 实现的计数排序分组，存储到 bucket 里
  for (string *iter = first; iter != last; ++iter) {
    char ch = (*iter)[offset];  // 获取字符串 *iter 的第 offset 个关键字
    size_t idx = ch;
    bucket[idx].push(*iter);  // 将字符串放进对应的 bucket 里
  }

  // 倒回原数组，iter 记录当前数组末端的位置
  string *iter = first;
  borders[0] = first;

  // 由于已知 0 < 1 < ... < MAXBUCKET-1，所以按关键字从小到大清空各个 bucket
  // 即可完成基于第 offset 个关键字的排序
  for (size_t idx = 0; idx < MAXBUCKET; ++idx) {
    // 清空第 idx 个 bucket
    while (!bucket[idx].empty()) {
      *iter++ = bucket[idx].front();
      bucket[idx].pop();
    }

    // 记录当前组的右边界，左边界 border[idx] 已经事先记录过了
    borders[idx + 1] = iter;
  }

  // 递归对具有相同关键字的元素进行下一关键字的排序
  for (int idx = 0; idx < MAXBUCKET; ++idx)
    if (borders[idx] != borders[idx + 1])  // 非空
      MSD_radix_sort(borders[idx], borders[idx + 1], offset + 1);
}

由于两个字符串的比较很容易冲上的线性复杂度，因此在字符串排序这件事情上，MSD 基数排序比大多数基于比较的排序算法在时间复杂度和实际用时上都更加优秀。

与桶排序的关系

前置知识：桶排序

桶排序需要其它的排序算法来完成对每个桶内部元素的排序。但实际上，完全可以对每个桶继续执行桶排序，直至某一步桶的元素数量 $\le 1$ 。

因此 MSD 基数排序的另一种理解方式是：使用桶排序实现的桶排序。

也因此，可以提出 MSD 基数排序在时间常数上的一种优化方法：假如到某一步桶的元素数量 $\le B$ （是自己选的常数），则直接执行插入排序然后返回，降低递归次数。

LSD 基数排序

MSD 基数排序从第关键字到第关键字顺序进行比较，为此需要借助递归或迭代来实现，时间常数还是较大，而且在比较自然数上还是略显不便。

而将递归的操作反过来：从第关键字到第关键字顺序进行比较，就可以得到 LSD（Least Significant Digit first）基数排序，不使用递归就可以完成的排序算法。

算法流程

将待排序的元素拆分为个关键字，然后先对 所有元素 的第关键字进行稳定排序，再对 所有元素 的第关键字进行稳定排序，再对 所有元素 的第关键字进行稳定排序……最后对 所有元素 的第关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。

一个 LSD 基数排序全流程的例子

LSD 基数排序也需要借助一种 稳定算法 完成内层对关键字的排序。同样的，通常使用计数排序来完成。

LSD 基数排序的正确性可以参考《算法导论（第三版）》第 8.3-3 题的解法或参考下面的解释：

正确性

回顾一下 k - 关键字元素的比较方法，

假如想通过和就比较出两个元素和的大小，则需要提前知道通过比较和得到的结论，以便于应对的情况；
而想通过和就比较出两个元素和的大小，则需要提前知道通过比较和得到的结论，以便于应对的情况；
……
而想通过 $a_{k-1}$ 和 $b_{k-1}$ 就比较出两个元素和的大小，则需要提前知道通过比较和得到的结论，以便于应对 $a_{k-1} = b_{k-1}$ 的情况；
和可以直接比较。

现在，将顺序反过来：

和可以直接比较；
而知道通过比较和得到的结论后，就可以得到比较 $a_{k-1}$ 和 $b_{k-1}$ 的结论；
……
而知道通过比较和得到的结论后，就可以得到比较和的结论；
而知道通过比较和得到的结论后，就最终得到了比较和的结论。

在这个过程中，对每个关键字边比较边重排元素的顺序，就得到了 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【模板】快速排序

给出个正整数，从小到大输出。

#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)$ ，其中为第关键字的值域大小。如果关键字值域很大，就可以直接使用基于比较的 $O(nk\log n)$ 排序而无需使用基数排序了。

空间复杂度

MSD 基数排序和 LSD 基数排序的空间复杂度都为。

参考资料与注释

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. ↩

本页面最近更新：2023/3/18 20:07:19，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：NachtgeistW, Alisahhh, countercurrent-time, Early0v0, Enter-tainer, H-J-Granger, hly1204, iamtwz, Ir1d, Konano, ksyx, ouuan, partychicken, sbofgayschool, SukkaW, untitledunrevised
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用