基数排序

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

int n, a[N], cnt[15], b[N];

void countSortByDigit(int n, int arr[], int exp)
{
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; i++)
    {
        int digit = (arr[i] / exp) % 10; // 获取当前位的数字
        cnt[digit]++;                    // 统计当前位的数字出现的次数
    }
    for (int i = 1; i <=9; i++)
        cnt[i] += cnt[i - 1]; // 计算当前位数字的累积次数
    for (int i = n; i >= 1; i--)
    {
        int digit = (arr[i] / exp) % 10; // 获取当前位的数字
        b[cnt[digit]--] = arr[i];        // 将当前位的数字按照累积次数放入结果数组
    }
    for (int i = 1; i <= n; i++)
        arr[i] = b[i]; // 将结果数组复制回原数组
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int maxNum = *max_element(a + 1, a + n + 1); // 找到数组中的最大值
    for (int exp = 1; exp <= maxNum; exp *= 10)
        countSortByDigit(n, a, exp);
    for (int i = 1; i <= n; i++)
            printf("%d ", a[i]);
    return 0;
}