1#include <bits/stdc++.h>
2using namespace std;
3
4// 获取数字 x 在第 exp 位上的值（exp = 1, 10, 100, ...）
5int getDigit(int x, int exp) {
6    return (x / exp) % 10;
7}
8
9// 对数组按第 exp 位进行计数排序（稳定排序）
10void countingSortByDigit(int a[], int n, int exp) {
11    int output[100005];
12    int count[10] = {0};
13
14    // 统计每个数字出现的次数
15    for (int i = 0; i < n; i++)
16        count[getDigit(a[i], exp)]++;
17
18    // 计算前缀和，确定每个数字的最终位置
19    for (int i = 1; i < 10; i++)
20        count[i] += count[i - 1];
21
22    // 从后往前遍历，保证稳定性
23    for (int i = n - 1; i >= 0; i--) {
24        int d = getDigit(a[i], exp);
25        output[count[d] - 1] = a[i];
26        count[d]--;
27    }
28
29    // 复制回原数组
30    for (int i = 0; i < n; i++)
31        a[i] = output[i];
32}
33
34void radixSort(int a[], int n) {
35    // 找到最大值，确定最大位数
36    int maxVal = *max_element(a, a + n);
37
38    // 从个位到最高位，逐位排序
39    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
40        countingSortByDigit(a, n, exp);
41    }
42}
43
44int main() {
45    int a[] = {170, 45, 75, 90, 802, 24, 2, 66};
46    int n = 8;
47
48    radixSort(a, n);
49
50    for (int i = 0; i < n; i++)
51        printf("%d ", a[i]);
52    // 输出: 2 24 45 66 75 90 170 802
53    return 0;
54}

1#include <bits/stdc++.h>
2using namespace std;
3
4// 获取 x 的第 pos 位（从高位数起，pos=0 为最高位）
5int getDigitMSD(int x, int pos, int maxDigits) {
6    int exp = 1;
7    for (int i = 0; i < maxDigits - 1 - pos; i++) exp *= 10;
8    return (x / exp) % 10;
9}
10
11void msdRadixSort(vector<int>& a, int pos, int maxDigits) {
12    if (a.size() <= 1 || pos >= maxDigits) return;
13
14    // 按当前位分桶
15    vector<vector<int>> buckets(10);
16    for (int x : a) {
17        int d = getDigitMSD(x, pos, maxDigits);
18        buckets[d].push_back(x);
19    }
20
21    // 递归排序每个桶
22    for (auto& bucket : buckets) {
23        msdRadixSort(bucket, pos + 1, maxDigits);
24    }
25
26    // 收集结果
27    int idx = 0;
28    for (auto& bucket : buckets) {
29        for (int x : bucket) {
30            a[idx++] = x;
31        }
32    }
33}
34
35int main() {
36    vector<int> a = {170, 45, 75, 90, 802, 24, 2, 66};
37
38    int maxVal = *max_element(a.begin(), a.end());
39    int maxDigits = 0;
40    while (maxVal > 0) { maxDigits++; maxVal /= 10; }
41
42    msdRadixSort(a, 0, maxDigits);
43
44    for (int x : a) printf("%d ", x);
45    // 输出: 2 24 45 66 75 90 170 802
46    return 0;
47}

1void radixSort256(int a[], int n) {
2    int output[100005];
3    for (int shift = 0; shift < 32; shift += 8) {
4        int count[256] = {0};
5        for (int i = 0; i < n; i++)
6            count[(a[i] >> shift) & 0xFF]++;
7        for (int i = 1; i < 256; i++)
8            count[i] += count[i - 1];
9        for (int i = n - 1; i >= 0; i--) {
10            int d = (a[i] >> shift) & 0xFF;
11            output[--count[d]] = a[i];
12        }
13        for (int i = 0; i < n; i++) a[i] = output[i];
14    }
15}