//桶排序
//原理：要对数组a[n]进行排序，新建一个b[9][n-1]的二维数组，
//把a中的元素分别放到数组b中，原则为：
//1．根据a中元素个位数的数字放到b中相应的行，如3则放到b中的第三行，100放到第0行
//此过程称为分布,用分布函数distributeElments()实现
//2．将b中的元素按照顺序复制回a中,此过程称为回收,用回收函数collectElments()实现
//3.然后依次按照a中元素的十位,百位...重复上述过程.其中如3的十位为0
//用函数numOfDigits()求得a中最大数的位数.

#include<iostream.h>

int a[]={1,255,8,6,25,47,14,35,58,75,96,158,657};
const int len=sizeof(a)/sizeof(int)-1;
int b[9][len]={0};//将b全部置0

void bucketSort(int a[]); //桶排序函数
void distributeElments(int a[],int b[9][len],int digits);
void collectElments(int a[], int b[9][len]);
int numOfDigits(int a[]);
void zeroBucket(int b[9][len]); //将b数组中的全部元素置0

void main()
{
 
 cout<<"原始数组：";
 for(int i=0; i<len; i++)
  cout<<a[i]<<",";
 cout<<endl;

 bucketSort(a);

 cout<<"排序后数组：";
 for(i=0; i<len; i++)
  cout<<a[i]<<",";
 cout<<endl;
}

void bucketSort(int a[])
{
 int digits=numOfDigits(a);

 for(int i=1; i<=digits; i++)
 {
  distributeElments(a,b,i);
  collectElments(a,b);

  if(i!=digits)
   zeroBucket(b);
 }
}

int numOfDigits(int a[])
{
 int largest=0;
 for(int i=0; i<len; i++) //获取最大值
 {
  if(a[i]>largest)
   largest=a[i];
 }

 int digits=0; //digits为最大值的位数

 while(largest)
 {
  digits++;
  largest/=10;
 }
 
 return digits;
 
}

void distributeElments(int a[],int b[9][len],int digits)
{
 int divisor=10; //除数

 for(int i=1; i<digits; i++)
  divisor*=10;

 for(int j=0; j<len; j++)
 {
  int numOfDigist=(a[j]%divisor-a[j]%(divisor/10))/(divisor/10);
 //numOfDigits为相应的(divisor/10)位的值,如当divisor=10时,求的是个位数
  int num=++b[numOfDigist][0];//用b中第一列的元素来储存每行中元素的个数
  b[numOfDigist][num]=a[j];
 }
}

void collectElments(int a[], int b[9][len])
{
 int k=0;
 for(int i=0; i<=9; i++)
  for(int j=1; j<=b[i][0]; j++)
  {
   a[k++]=b[i][j];
  }
}

void zeroBucket(int b[][len])
{
 for(int i=0; i<9; i++)
  for(int j=0; j<len; j++)
   b[i][j]=0;
}