首页 / 算法 / 从0开始学算法--排序（1.9基数排序）
从0开始学算法--排序（1.9基数排序）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了从0开始学算法--排序（1.9基数排序），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1689字，纯文字阅读大概需要3分钟。
内容图文
算法理解：
基数排序使对桶排序的一种优化，因为桶排序极不稳定，出现a[]={1，401，402，403，440，405}这种数据因为分桶的不合理时间复杂度退化到了O（n2）
于是牛人就想到了由低到高根据每一位上的数字分桶，比如上面提到的数据，由于最大数字使3位，所以要进行三次分桶。
第一次分桶,根据最低位分桶
0->440
1->1->401
2->402
3->403
4
5->405
6
7
8
9
第一次分桶完得到的数组：440，1，401，402，403，405
第二次根据十位数字分桶：
0->1->401->402->403->405
1
2
3
4->440
5
6
7
8
9
第二次分桶的结果1，401，402，403，405，440（数组已经有序0.0）
第三次根据百位数字分桶：
0->1
1
2
3
4->401->402->403->405->440
5
6
7
8
9
排序结果：1，401，402，403，405，440
参考代码：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
const int maxn=1e5+10;
int maxwei(int a[],int n){
int maxx=0;
for(int i=0;i<n;i++){
int count=1,tem=a[i];
while(tem/10!=0){
tem=tem/10;
count++;
}
if(count>maxx)
maxx=count;
}
return maxx;
}
void basesort(int a[],int n){
int maxx=maxwei(a,n); //取得最大位数
int num=1;
for(int i=0;i<maxx;i++){
int count[10]; //声明count为了统计每个桶放了几个数
int temp[10][1000]; //temp相当于桶，前一个数标记第几个篮子，后一个为了标记放的个数
for(int f=0;f<10;f++){
count[f]=0;
}
for(int g=0;g<10;g++){
for(int z=0;z<n;z++){
temp[g][z]=0;
}
}
for(int j=0;j<n;j++){
int fg=a[j]/num;
int k=fg%10;
count[k]++;
int te=count[k]-1;
temp[k][te]=a[j];
}
int b=0;
for(int h=0;h<10;h++){
if(count[h]>0){
for(int v=0;v<count[h];v++){
a[b]=temp[h][v];
b++;
}
}
}
num=num*10;
}
}
void print(int a[],int n){
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
printf("\n");
}
int main(){
int a[maxn];
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
basesort(a,n);
print(a,n);
return 0;
}
内容总结
以上是互联网集市为您收集整理的从0开始学算法--排序（1.9基数排序）全部内容，希望文章能够帮你解决从0开始学算法--排序（1.9基数排序）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。