#include <iostream>

using namespace std;

const int N = 100010;

int q[N], w[N], s[N], n;

void radix_sort(int d, int r)
{
    int radix = 1;
    for(int i = 1; i <= d; i ++)
    {
        for(int j = 0; j < r; j ++) s[j] = 0;
        for(int j = 0; j < n; j ++) s[q[j] / radix % r] ++;
        for(int j = 1; j < r; j ++) s[j] += s[j - 1];
        for(int j =  n - 1; j >= 0; j --) w[ --s[q[j] / radix % r]] = q[j];
        for(int j = 0; j < n; j ++) q[j] = w[j];
        radix *= r;
    }
}

int main()
{
    cin >> n;

    for(int i = 0; i < n; i ++) cin >> q[i];

    radix_sort(10, 10);

    for(int i = 0; i < n; i ++) cout << q[i] << " ";
    return 0;
}

https://www.bilibili.com/video/BV17t411v7fT/?vd_source=461ee971d767a3490aace7fbf9394d53