#include<stdio.h>
#include<math.h>
int getlooptimes(int num)
{
int count = 1;
int temp = num/10;
while(temp!=0)
{
count++;
temp = temp/10;
}
return count;
}
int findmaxnum(int *p,int n)
{
int i;
int max = 0;
for(i = 0;i<n;i++)
{
if(*(p+i)>max)
{
max = *(p+i);
}
}
return max;
}
void sort2(int *p,int n,int loop) //*p为排序数组，n为数组长度，loop为分配次数
{
int buckets[10][20] = {}; //定义的缓存区：桶
int tempnum = (int)pow(10,loop-1);
//如798个位桶index=(798/1)=8
//十位桶index=(798/10)=9
//百位桶index=(798/100)=7
//tempNum为上式中的1、10、100
int i,j;
for(i = 0;i<n;i++)
{
int row_index = (*(p+i)/tempnum); //关键步骤之一
for(j = 0;j<20;j++)
{
if(buckets[row_index][j] == 0)
{
buckets[row_index][j] = *(p+i); //关键步骤之二
break;
}
}
}
//将buckets中的数倒回到原数组当中
int k = 0;
for(i = 0;i<10;i++)
{
for(j = 0; j<20; j++)
{
if(buckets[i][j]!=0)
{
*(p+k)=buckets[i][j]; //关键步骤之三
buckets[i][j] = 0; //清空
k++;
}
}
}
}
void bucketsort3(int *p,int n)
{
int maxnum = findmaxnum(p,n); //获取数组中最大值
printf("maxnum=%d\n",maxnum);
int looptimes = getlooptimes(maxnum); //获取最大数的位数，即分配次数
printf("looptimes=%d\n",looptimes);
int i;
for(i = 1;i<=looptimes;i++) //对个、十、百、千、万......位进行排序
{
sort2(p,n,i);
}
}
int main()
{
int a[] = {2,343,342,1,123,43,4343,433,687,0,654,3,80};
int *a_p = a;
int size = sizeof(a)/sizeof(int);
bucketsort3(a_p,size); //基数排序
int i;
for(i = 0; i < size ; i++)
printf("%d\n",a[i]);
return 0;
}
