基数排序笔记

基数排序是一种非比较型排序算法，他根据数字的每一位来排序，通常用于整数排序，通过若干次“分配”，“收集”来实现

算法思想：

1获取待排序元素最大值，并确定其位数

2从最低位开始，依次对所有元素“分配”和“收集”操作

3在每一位上，根据该位上的数字的值将元素分配到相应的桶里（十进制就建十个桶）

4对每个桶的元素顺序排序

重复上述步骤直到所有位都进行了排序

演示：

时间复杂度：O(d(n+r)),d是数字位数，n是待排元素数量，r是基数位数较少效率较高，空间复杂度：需要额外空间，具体空间取决于桶的数量和存储桶的方式，很容易排有固定宽度的数字序列。

int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
int maxData = data[0]; ///< 最大数
/// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
for (int i = 1; i < n; ++i)
{
if (maxData < data[i])
maxData = data[i];
}
int d = 1;
int p = 10;
while (maxData >= p)
{
//p *= 10; // Maybe overflow
maxData /= 10;
++d;
}
return d;
/* int d = 1; //保存最大的位数
int p = 10;
for(int i = 0; i < n; ++i)
{
while(data[i] >= p)
{
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中的位置依次分配给每个桶
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;
}