以一个数为基数 b b b，然后第 k k k 次按照在 b b b 进制下的第 k k k 位来排序。
例如有
12
12
12 个数：
13 23 34 27 19 37 43 22 11 9 21 40
取
b
=
10
b=10
b=10，也就是十进制。
当
k
=
1
k=1
k=1 时，排序结果如下：
40 11 21 22 13 23 43 34 27 37 19 9
现在这些数已经按照个位排好序了，接下来，当
k
=
2
k=2
k=2时，排序结果如下：
9 11 13 19 21 22 23 27 34 37 40 43
这时候，由于最大的数只有两位，所以现在已经排好序了。
多开一维空间，大小为b
排序过程如下：
创建一个大小为
b
∗
N
b*N
b∗N（N为待排数组的数据总个数）的二维数组cnt，循环从
k
=
1
k=1
k=1开始依次递增，每次循环看第i个数的第k位数字m，将这个数放在cnt[m, i]上。
-
k=1
13是第1个数，1位是3，放在cnt[3, 1]
23是第2个数，1位是3，放在cnt[3, 2]
34是第3个数，1位是4，放在cnt[4, 3]
27是第4个数，1位是7，放在cnt[7, 4]
…
遍历完所有数之后，按cnt[0, j]、cnt[1, j]、cnt[2, j]、…、cnt[9, j]依次取出数字，就可以得到按照第1位排好序的序列。 -
k = 2
40是第1个数，2位是4，放在cnt[4, 1]
11是第2个数，2位是1，放在cnt[1, 2]
…
9是第12个数，2位是0（不存在这位就当作0），放在cnt[0, 9]
同上按cnt[0, j]、cnt[1, j]、cnt[2, j]、…、cnt[9, j]依次取出数字，就可以得到按照第2位排好序的序列。
#include <iostream>
#include <cstring>
using namespace std;
int n, a[100005], cnt[15][100005];
int main() {
scanf("%d", &n);
int max_a = 0;
for (int i = 0; i < n; i ++ ) {
scanf("%d", &a[i]);
max_a = max(max_a, a[i]);
}
int p = 1;
while (max_a) {
memset(cnt, 0, sizeof cnt);
for (int i = 0; i < n; i ++ ) cnt[(a[i] / p) % 10][i] = a[i];
int l = 0;
for (int i = 0; i < 10; i ++ ) {
for (int j = 0; j < n; j ++ ) {
if (cnt[i][j]) a[l ++ ] = cnt[i][j];
}
}
p *= 10;
max_a /= 10;
}
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
return 0;
}
省去多开的一维空间
事实上，并不需要额外开一维空间，我们只需要用cnt记录第k位数字是0、1、2、3、…的数各自总共有多少个，然后求前缀和即可把这些数都放在同一个数组b中。
例如第1位里，是0的有1个，是1的有3个，是2的有4个，是3的有2个。则cnt[0]=1，cnt[1]=3，cnt[2]=4，cnt[3]=2。
求前缀和后：cnt[0]=1，cnt[1]=4，cnt[2]=8，cnt[3]=10。
那么第1位是0的放在b[0]，是1的放在b[1 ~ 3]，是2的放在b[4 ~ 7]，是3的放在b[8 ~ 9]。即第1位是m的，放在b[cnt[m - 1]] 至 b[cnt[m] - 1]中
时间复杂度为 O ( ( n + b ) l o g b n ) O((n+b)log_{b}n) O((n+b)logbn)，空间复杂度为 O ( n + b ) O(n+b) O(n+b)，看上去不是线性，但是非常接近线性。
#include <iostream>
#include <cstring>
using namespace std;
int n, a[100005], cnt[15], b[100005];
int main() {
scanf("%d", &n);
int max_a = 0;
for (int i = 0; i < n; i ++ ) {
scanf("%d", &a[i]);
max_a = max(max_a, a[i]);
}
int p = 1;
while (max_a) {
memset(cnt, 0, sizeof cnt);
for (int i = 0; i < n; i ++ ) cnt[(a[i] / p) % 10] ++ ;
for (int i = 1; i < 10; i ++ ) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; i -- ) { // 从后往前扫a，同时cnt从高往低减，b从后往前放，等价于正着做
int m = a[i] / p % 10;
b[cnt[m] - 1] = a[i];
cnt[m] -- ;
}
for (int i = 0; i < n; i ++ ) {
a[i] = b[i];
}
p *= 10;
max_a /= 10;
}
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
return 0;
}
采用256进制作为基数
事实上，在实际中， b b b 不会取 10 10 10，因为模运算的效率极低， b b b 通常取 256 256 256，这样在 2 32 2^{32} 232 的数以内，只需要排 4 4 4次。 b b b 不取 65536 65536 65536 的原因是为了卡进一级缓存，效率更高。
#include <iostream>
#include <cstring>
using namespace std;
int n, a[100005], cnt[260], b[100005];
int main() {
scanf("%d", &n);
int max_a = 0;
for (int i = 0; i < n; i ++ ) {
scanf("%d", &a[i]);
}
//for (int i = 0; max_a > ((long long)1 << i); i += 8) { // 256 = 2 ^ 8
for (int i = 0; i <= 30; i += 8) {
memset(cnt, 0, sizeof cnt);
for (int j = 0; j < n; j ++ ) cnt[(a[j] >> i) & 255] ++ ;
for (int j = 1; j < 256; j ++ ) cnt[j] += cnt[j - 1];
for (int j = n - 1; j >= 0; j -- ) { // 从后往前扫a，同时cnt从高往低减，b从后往前放，等价于正着做
b[ -- cnt[(a[j] >> i) & 255]] = a[j];
}
for (int j = 0; j < n; j ++ ) a[j] = b[j];
}
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
return 0;
}