基数排序（Radix Sort）与快速排序不同，是一种非比较的排序算法，本质上属于一种特殊的桶排序，将桶的范围缩小到了$|\sum|$个，其中$|\sum|$为偏序字符集的大小（对于整型而言就是10）。

算法的核心思想是从低位到高位（高位到低位）按位比较。

例如对于以下序列

$$1,23,456,34,798,97$$

算法首先比较其个位（或最高位百位），放入桶中

依次取出，序列变为

$$1,23,34,456,97,798$$

再对十位进行同样的操作

序列变为

$$1,23,34,456,97,798$$

同样的操作再对百位进行一次，序列变为

$$1,23,34,97,456,798$$

即为最终排序结果。

需要注意的是，取出与放入是存在顺序的。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;

int n;
int d[N];

void radix_sort(int data[], int n, int maxn) {
    int max_bit = 0;
    for ( ; maxn; maxn /= 10)
        ++max_bit;

    int count[10], temp[n], radix = 1;
    for ( int i = 1; i <= max_bit; ++i ) {
        memset(count, 0, sizeof count);
        for ( int j = 0; j < n; ++j )
            ++count[(data[j] / radix) % 10];

        for ( int j = 1; j < 10; ++j )
            count[j] = count[j - 1] + count[j];

        for ( int j = n - 1; j >= 0; --j ) {
            int k = (data[j] / radix) % 10;
            temp[count[k] - 1] = data[j];
            --count[k];
        }

        for ( int j = 0; j < n; ++j )
            data[j] = temp[j];

        radix *= 10;
    }
}

int main() {
    scanf("%d", &n);

    int maxn = 0;
    for ( int i = 0; i < n; ++i ) {
        scanf("%d", &d[i]);
        maxn = max(maxn, d[i]);
    }

    radix_sort(d, n, maxn);

    for ( int i = 0; i < n; ++i )
        printf("%d ", d[i]);

    return 0;
}

算法性能

算法时间复杂度$O(kn)$，空间复杂度$O(k+n)$，其中$k$为数字位数，$n$为排序元素个数。