$$
\color{#614ad3}{基数排序,其实就是将p进制数按照该数的每一位进行排序(自低位往高位排)}
$$
这其实是按照$\color{#e42c64}{多个关键字}$进行计数排序.
比如将(10进制)1323,91153的按照不减的顺序排列.
- 按照个位进行排列-> 1323, 91153
- 按照十位进行排列-> 91153, 1323
- 按照百位进行排列-> 1323, 91153
- 按照千位进行排列-> 1323, 91153
- 按照万位进行排列-> 91153, 01323(没有则用0补齐)
可以看出低位关键字其实优先级较高位关键字低,所以$\color{#ff585d}{先排低位关键字}$
另外可以看到,这种思路,做正整数的排序较为简单,负数有点麻烦(其实我没查资料(●’◡’●))
下面基于int内非负整数(0~2^31-1)的排序给出模板
其中:
- 基数是256,256进制
- 小技巧(
似乎没什么用):
$$ \color{#001871}{\boxed{\color{#ffb549}{x\%2^p=x\&(2^p-1)}}} $$
注:$\%256\Leftrightarrow \&255$
void radix_sort()
{
int tmp[N];// 临时存储基于某个关键字排序后的结果
int bucket[256];// 桶
for(int i = 0;i < 32;i += 8)// 用移8位来得到256进制数的下一'位'
{
memset(bucket,0,sizeof bucket);
for(int j = 0;j < n;j ++) bucket[(q[j] >> i) % 256] ++;// 计数
for(int j = 0,sum = 0;j < 256;j ++)// 得到计数数组的前缀和
sum += bucket[j],bucket[j] = sum - bucket[j];// 在这种写法可以避免bucket[-1]
for(int j = 0;j < n;j ++)
tmp[bucket[(q[j] >> i) % 256] ++] = q[j];// 计数排序
memcpy(q,tmp,sizeof tmp);//memcpy要比swap快一点,memcpy定义在cstring库内
}
}
十进制下,9位关键字以内[0,10^9)内的基数排序
void radix_sort()
{
int tmp[N],bucket[10],p = 1;
for(int i = 0;i < 9;i ++)
{
memset(bucket,0,sizeof bucket);
for(int j = 0;j < n;j ++) bucket[q[j] / p % 10] ++;
for(int j = 0,sum = 0;j < 10;j ++)
sum += bucket[j],bucket[j] = sum - bucket[j];
for(int j = 0;j < n;j ++) tmp[bucket[q[j] / p % 10]++] = q[j];
memcpy(q,tmp,sizeof tmp);
p *= 10;
}
}