输入:
第一行 n, 表示 n个非负整数
第二行,n 个数
输出:
这n个数排好序后的结果
基数排序的思路分析:
从个位开始,以各位数(0-9) 做为关键字进行分桶,然后再收集
重复这个动作,直至到最高位为止。最高位不够的填0处理
比如下面的这个用例:
10
434 22234 43 983 8 98 34 12 3 111
模拟一下:
第一阶段:
第二阶段:
第三阶段:
第四阶段:
第五阶段:
代码如下:
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> arr;
int n;
int getBits(int x){
int res = 0;
while (x)
{
res++;
x/=10;
}
return res;
}
int main(){
scanf("%d",&n);
int maxBit = 0;
for(int i=1;i<=n;i++){
int a;
scanf("%d",&a);
maxBit = max(maxBit,getBits(a));
arr.push_back(a);
}
int baseBit = 1;
for(int i=0;i<maxBit;i++){
vector<int> bbulket[10];
for(auto& v:arr){
int digit = (v/baseBit)%10;
bbulket[digit].push_back(v);
}
baseBit*=10;
//收集
arr.clear();
for(int i=0;i<10;i++){
for(int j=0;j<bbulket[i].size();j++){
arr.push_back(bbulket[i][j]);
}
}
}
for(auto&v:arr){
printf("%d ",v);
}
printf("\n");
return 0;
}