C/C++基数排序（Radix Sort） 的排序算法。

一、代码解释与实现功能：

基数排序是一种非比较型整数排序算法，它通过将整数按位数切割成不同的数字，然后按每个位数分别进行比较和排序。

1. 输入数据：

   • 用户输入一个整数 n，表示数组的长度。

   • 然后输入 n 个整数，存储在数组 a 中。

   • 同时，代码会找到数组中的最大值 max，并计算最大值的位数 num（即需要排序的轮数）。

2. 基数排序：

   • 代码通过 rs 函数实现基数排序。

   • 每一轮排序根据当前位数（个位、十位、百位等）对数组进行排序。

   • 排序过程中使用计数排序（Counting Sort）作为子程序，确保每一轮排序的稳定性。

3. 输出结果：

   • 每一轮排序后，代码会输出当前排序的结果。

   • 最终，数组 a 会被完全排序。

二、具体代码展示：

#include<bits/stdc++.h>
using namespace std;
void rs(int a[],int n,int num)
{
    int b=1;
    for(int i=0;i<num;i++)
    {
        int past[1000];
        int s[10]={0};
        for(int i=0;i<n;i++)
            s[(a[i]/b)%10]++;
        for(int i=1;i<n;i++)
            s[i]+=s[i-1];
        for(int i=n-1;i>=0;i--)
            past[--s[(a[i]/b)%10]]=a[i];
        for(int i=0;i<n;i++)
            cout<<past[i]<<' ';
        cout<<endl;
        for(int i=0;i<n;i++)
            a[i]=past[i];
        b*=10;
    }
}
int main()

{
    int n,max=0,num=0;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(max<a[i])
            max=a[i];
    }
    while(max>0)
    {
        max/=10;
        num++;
    }
    rs(a,n,num);
}

具体行解释：

int main()
{
    int n, max = 0, num = 0;
    cin >> n; // 输入数组长度
    int a[n]; // 定义数组
    for (int i = 0; i < n; i++)
    {
        cin >> a[i]; // 输入数组元素
        if (max < a[i])
            max = a[i]; // 找到最大值
    }
    while (max > 0)
    {
        max /= 10;
        num++; // 计算最大值的位数
    }
    rs(a, n, num); // 调用基数排序函数
}

• 输入数组并找到最大值。

• 计算最大值的位数 num，决定需要多少轮排序。

• 调用 rs 函数进行排序。

void rs(int a[], int n, int num)
{
    int b = 1; // b 表示当前位数（1, 10, 100, ...）
    for (int i = 0; i < num; i++) // 按位数进行排序
    {
        int past[1000]; // 临时数组，用于存储排序结果
        int s[10] = {0}; // 计数数组，用于计数每个数字（0-9）的出现次数

        // 统计当前位数的数字出现次数
        for (int i = 0; i < n; i++)
            s[(a[i] / b) % 10]++;

        // 计算前缀和，确定每个数字的最终位置
        for (int i = 1; i < 10; i++)
            s[i] += s[i - 1];

        // 将元素按当前位数排序到临时数组 past 中
        for (int i = n - 1; i >= 0; i--)
            past[--s[(a[i] / b) % 10]] = a[i];

        // 输出当前排序结果
        for (int i = 0; i < n; i++)
            cout << past[i] << ' ';
        cout << endl;

        // 将排序结果复制回原数组 a
        for (int i = 0; i < n; i++)
            a[i] = past[i];

        b *= 10; // 处理下一位
    }
}

• 每一轮排序：

  1. 统计当前位数的数字（0-9）出现次数。

  2. 计算前缀和，确定每个数字的最终位置。

  3. 将数组元素按当前位数排序到临时数组 past 中。

  4. 输出当前排序结果。

  5. 将排序结果复制回原数组 a。

• 重复上述过程，直到所有位数处理完毕。

三、运行结果示例

总结

• 这个代码实现了基数排序算法，能够对整数数组进行排序。

• 每一轮排序基于当前位数（个位、十位、百位等），使用计数排序确保稳定性。

• 代码的时间复杂度为 O(k * n)，其中 k 是最大值的位数，n 是数组长度。