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

news/2025/3/14 14:11:37/

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

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

输入数据：
- 用户输入一个整数 n，表示数组的长度。
- 然后输入 n 个整数，存储在数组 a 中。
- 同时，代码会找到数组中的最大值 max，并计算最大值的位数 num（即需要排序的轮数）。
基数排序：
- 代码通过 rs 函数实现基数排序。
- 每一轮排序根据当前位数（个位、十位、百位等）对数组进行排序。
- 排序过程中使用计数排序（Counting Sort）作为子程序，确保每一轮排序的稳定性。
输出结果：
- 每一轮排序后，代码会输出当前排序的结果。
- 最终，数组 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;// 将排序结果复制回原数组 afor (int i = 0; i < n; i++)a[i] = past[i];b *= 10; // 处理下一位}
}