东方博宜OJ 1010：数组元素的排序 ← 基数排序

【题目来源】 https://oj.czos.cn/p/1010 【题目描述】 对数组的元素按从小到大进行排序。 【输入格式】 第一行有一个整数 n（5≤n≤10）； 第二行有 n 个整数，每个整数的值在 [0, 10^9]的范围内。 【输出格式】 输出排序后的数组。 【输入样例】 8 1 2 3 6 8 7 4 5 【输出样例】 1 2 3 4 5 6 7 8 【数据范围】 5≤n≤10 【算法分析】 ● 基数排序（Radix Sort）（https://blog.csdn.net/hnjzsyjyj/article/details/153932655）是一种‌非比较型整数排序算法‌，通过逐位分配和收集元素实现排序‌。基数排序仅适用于整数或可转换为数字的字符串‌的排序。其核心原理是将整数按位数切割，从最低位（LSD）或最高位（MSD）开始依次排序，利用桶排序或计数排序作为子过程‌。基数排序是倍增法实现后缀数组（Suffix Array）的核心排序工具，其高效的 O(n) 时间复杂度直接决定了后缀数组整体算法的时间复杂度‌。 【算法代码：基数排序】

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

const int maxn=1e5+5;
int a[maxn];
int rk[maxn],freq[maxn];

int maxbit(int n,int a[]) {
int imax=0;
for(int i=1; i<=n; i++) {
int cnt=0, t=a[i];
while(t!=0) {
t=t/10;
cnt++;
}
imax=max(imax,cnt);
}
return imax;
}

void Radix_Sort(int n,int a[]) {
int cnt=maxbit(n,a);
int div=1;
while(cnt–) {
for(int i=0; i<=9; i++) {
freq[i]=0;
}

for(int i=1; i<=n; i++) {
int t=(a[i]/div)%10;
freq[t]++;
}

for(int i=1; i<=9; i++) {
freq[i]+=freq[i-1];
}

for(int i=n; i>=1; i–) {
int t=(a[i]/div)%10;
rk[freq[t]]=a[i];
freq[t]–;
}

for(int i=1; i<=n; i++) {
a[i]=rk[i];
}

div=div*10;
}
}

int main() {
int n;
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i];
}

Radix_Sort(n,a);

for(int i=1; i<=n; i++) {
cout<<a[i]<<" ";
}

return 0;
}

/*
in:
5
6 9 2 7 1

out:
1 2 6 7 9
*/

【参考文献】 https://blog.csdn.net/hnjzsyjyj/article/details/161347829 https://blog.csdn.net/hnjzsyjyj/article/details/161332702 https://blog.csdn.net/hnjzsyjyj/article/details/161346075 https://blog.csdn.net/hnjzsyjyj/article/details/161588834 https://blog.csdn.net/hnjzsyjyj/article/details/161798997