基数排序 - StarCried 的狼窝

算法描述

基数排序（又叫做桶排序）是一种非比较排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别进行排序。

基数排序的步骤如下：

找出最大数，确定位数。
确定每个位数的范围，并统计每个数字在每个位数上的数量。
位数从低到高按每个位数从小到大进行排序。
输出排序后的数组。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctype.h>
using namespace std;
inline int read()
{
    int x=0,w=0;char c=getchar();
    while(!isdigit(c))w|=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return w?-x:x;
}
const int maxn=1e5+10;
int a[maxn],buck[maxn];
inline int get_max(int a[],int n)
{
    int maxx=0;
    for(int i=0;i<n;i++)
    maxx=max(maxx,a[i]);
    return maxx;
}
inline void count_sort(int a[],int n,int exp)
{
    int output[n],buck[10]={0};
    for(int i=0;i<n;i++)
        buck[(a[i]/exp)%10]++;
    for(int i=1;i<10;i++)
        buck[i]+=buck[i-1];
    for(int i=n-1;i>=0;i--)
        output[--buck[(a[i]/exp)%10]]=a[i];
    for(int i=0;i<n;i++)
        a[i]=output[i];
}
inline void radix_sort(int a[],int n)
{
    int maxx=get_max(a,n);
    for(int i=1;(maxx/i)>0;i*=10)
        count_sort(a,n,i);
}
int main()
{
    int n=read();
    for(int i=0;i<n;i++)
    a[i]=read();
    radix_sort(a,n);
    for(int i=0;i<n;i++)
        if(i!=n)printf("%d ",a[i]);
        else printf("%d\n",a[i]);
    return 0;
}