桶排序

桶排序假设输入数据服从均匀分布，平均情况下它的时间代价为O(n)；它的工作原理就是将数组分到有限数量的桶子里，每个桶子在使用其他排序算法或者递归的方式使用桶排序。

假如要对大小为[1…1000]范围内的n个数进行排序，可以把桶的大小设为10，那么就会产生100个桶。把输入的n个元素依次放到与之对应的桶中，然后对每个桶在进行排序，这样我们依次输出每个桶中的数据就得到了一个排序好的序列。将元素通过恰当的映射关系将元素尽量等数量的分到各个桶里面，这个映射关系就是桶排序算法的关键。桶标记的大小也要和值区间有对应关系。

对于桶排序的效率来说，待排序元素越均匀，桶排序的效率越高。数据均匀意味着每个桶在中间过程中容纳的元素个数都差不多，不会出现特别少或者特别多的情况。这样在排序子程序进行桶内排序的过程中会达到最优效率。但是实际应用的情况中，这种情况不会很理想的出现，所以桶排序在实际应用中的作用不是很大。

代码来自百度百科：

#include<iostream>
using namespace std;
int a[]= {1,255,8,6,25,47,14,35,58,75,96,158,657};
const int len=sizeof(a)/sizeof(int);
int b[10][len+1]= {0}; //将b全部置0
void bucketSort(int a[]);//桶排序函数
void distribute(int a[],int b[10][len+1],int digits);
void collectElments(int a[],int b[10][len+1]);
int numOfDigits(int a[]);
void zeroBucket(int b[10][len+1]);//将b数组中的全部元素置0
int main()
{
    cout<<"原始数组：";
    for(int i=0; i<len; i++)
        cout<<a[i]<<",";
    cout<<endl;
    bucketSort(a);
    cout<<"排序后数组：";
    for(int i=0; i<len; i++)
        cout<<a[i]<<",";
    cout<<endl;
    return 0;
}
void bucketSort(int a[])
{
    int digits=numOfDigits(a);      //返回最大值的位数
    for(int i=1; i<=digits; i++)
    {
        distribute(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 distribute(int a[],int b[10][len+1],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[10][len+1])
{
    int k=0;
    for(int i=0; i<10; i++)
        for(int j=1; j<=b[i][0]; j++)
            a[k++]=b[i][j];
}
void zeroBucket(int b[][len+1])
{
    for(int i=0; i<10; i++)
        for(int j=0; j<len+1; j++)
            b[i][j]=0;
}