概述

基数排序其实是一种桶排序，利用了桶排序的容器思想，把需要比较的逻辑值放入容器中，从而比较出大小。顾名思义，基数排序是根据基数来排序的，即根据个位十位百位... 的大小关系来排序。
需要注意，桶排序并不是一种具体的排序方法，而是一类排序的总称，只要运用了桶（容器）思想的排序都叫桶排序。
在具体谈论到基数排序前，我们先从桶排序的基础实现——计数排序讲起。

基本步骤

1. 从第一位（个位）开始，按照每个数的个位进行桶排序，得到一个大小关系，存储在数组 a 中；
2. 在第一位生成的 a 数组的基础上，按照第二位的大小再重新排序；
3. 同理，直到遍历完了所有的位数；

例如，我们以十进制为例，a 数组（原始数组）中的最大元素为 10010，共有 5 位，所以伪代码可以写成：

for (i = 1 to 5) // 位数
    // 进行桶排序
	for (v: a) // 取 a 中的每一个数的第i位
	    ...

基本思想

当我们按照第一位排序完成后，所有数，如果只看个位就是有序的。然后，进行第二轮。

第二轮实际上是在第一轮的基础上进行排序的，如果十位的存在，破坏了个位的排序，那么就更新这个数组。

例如，有数 316,224，在第一轮排序后，两个数的排序为 224, 316。在进行第二轮的时候，就会进行更新，由于第二位 ${\displaystyle 2>1}$，则这两个数的相对次序一定会更新成 316, 224。

我们只有遍历到其最后一位，才能最终确定这数的大小关系，也就是说，对于 316 和 224，只有遍历完了 3 位，才有可能得到其真正的大小关系。

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e6 + 10;
int n;
int a[N], s[N], w[N];

// 总共有d位, r 进制
void radix_sort(int d, int r) {
    int radix = 1;
    for (int i = 1; i <= d; i++) {
    	// 当前正在以r进制的第i位进行桶排序
        // 重置
        for (int j = 0; j < r; j++) s[j] = 0;
        // 对于第 i 位做桶排序
        for (int j = 0; j < n; j++) s[a[j] / radix % r] ++;
        // 前缀和
        for (int j = 1; j <= n; j++) s[j] += s[j - 1];
        // 计算位置
        for (int j = n - 1; j >= 0; j--) w[-- s[a[j] / radix % r]] = a[j];
        // 生成数组
        for (int j = 0; j < n; j++) a[j] = w[j];
        // 更新 radix, 以便于获取下一位的数字
        radix *= r;
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    radix_sort(10, 10);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}

for (int i = 1; i <= d; i++) {
	a[j] / radix % r;
	radix *= r;
}