排序之基数排序

基数排序：

　　基数排序的思想就是将待排数据中的每组关键字依次进行桶分配
基数排序：LSD和MSD方法。LSD的基数排序适用于位数小的数列，如果位数多，使用MSD效率会更高。
MSD与LSD相反，由高位数为基底开始分配。
LSD为例：73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中。
接下来将这些桶子中的数值重新串接起来，成为以下的数列：81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配，这次是根据十位数来分配：

int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)//复杂度(dN)
        {
            p *= 10;
            ++d;
        }
    }
    return d;
}

void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);//求得数组中所有的数据的最大位数
    int *tmp = new int[n];//存放每一位基数排序的结果
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;//关键字
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶，为count[k]在tmp中预留位置。把桶累计起来。
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];//把桶串起来
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;//每次更新关键字
    }
    delete[]tmp;
    delete[]count;
}