基数排序

//基数排序
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#define maxn 100
using namespace std;
int a[maxn];
int n=0;
int bits=0;
vector<int>  barrel[10];


int bitnum(int n)
{
    int result=0;
    while(n)
    {
        result++;
        n/=10;
    }
    return result;


}
void barrelsort_lsd()
{
    for(int i=1;i<=bits;i++)
    {
        for(int j=0;j<10;j++)
            barrel[j].clear();
        for(int j=0;j<n;j++)
        {
            int temp=a[j]/pow(10,i-1);
            temp=temp%10;
            barrel[temp].push_back(a[j]);
        }
        int index=0;
        for(int j=0;j<10;j++)
            for(vector<int>::iterator iter=barrel[j].begin();iter<barrel[j].end();iter++)
                a[index++]=*iter;
    }
    for(int i=0;i<n;i++)
        printf("%d   ",a[i]);
}


void barrelsort_msd(int* p,int right,int bit)
{
    int **q=(int **)malloc(10*sizeof(int *));
    for(int i=0;i<10;i++)
    {
        q[i]=(int *)malloc(maxn*sizeof(int));
        q[i][maxn-1]=0;
    }


    for(int i=0;i<right;i++)
    {
        int temp=p[i]/pow(10,bit-1);
        temp=temp%10;
        q[temp][q[temp][maxn-1]++]=p[i];
    }
    if(bit!=1)
        for(int i=0;i<10;i++)
            barrelsort_msd(q[i],q[i][maxn-1],bit-1);
    //合并操作
    int index=0;
    for(int i=0;i<10;i++)
    {
        for(int j=0;j<q[i][maxn-1];j++)
            p[index++]=q[i][j];
        delete[] q[i];
    }
    delete[] q;


}


int main()
{
    freopen("a.txt","r",stdin);
    while(scanf("%d",&a[n])!=EOF)
    {
        int t;
        bits=((t=bitnum(a[n])),bits<t?t:bits);
        n++;
    }


    barrelsort_lsd();
    printf("\n");
    barrelsort_msd(a,n,bits);
    for(int i=0;i<n;i++)
        printf("%d ",a[i]);


}