详谈基数排序

0. 基数排序由来

有一个学生记录数组，数组元素包含三个字段：系别，班号，班内编号。现在要对这个数组排序，使得系别小的在前，系别相同的班号小的在前，班号相同则班内编号较小的在前。这个排序与一般的排序要求（只对某个关键字段排序）不同的是：对多个关键字段排序。有2种方法可解决：一种是扫描一遍记录，将之按系别分组，再对组内记录按班号分组，然后对组内记录进行单关键字排序；另一种方法是，将这个数组按班内编号排序（班内编号在确定的范围内），然后再对整个数组按班号排序（班号在确定的范围内），最后对整个数组按系别排序（系别在确定的范围内）。第一种方法采取的策略是最高位优先排序。第二种方法采取分步骤按关键字类别排序的策略通常称为基数排序，可以看出基数排序的特点是各关键字段的分布是在确定范围（一般较小）内的。

对单关键字排序也可采用多关键字排序的思想：将单关键字分解成多个关键字段，在可控范围内，不用比较，直接排序。

计算机实现基数排序方式：分配和收集。按关键字段将记录重新分成若各组，再将各个组有序组合成新记录序列。

1. 基数排序图解

1.1 基数排序图示

1）辅助队列实现基数排序

不足：需要额外利用队列来辅助排序，存在空间浪费。

2）链队列实现基数排序

3）基于桶有序的基数排序（也称计数排序，统计子关键字的出现频率）

考虑一种简单情况，如果你给一些unsigned char 排序，除了教科书上的很多方法外，还有一种简单的。可以这样考虑，试想排一系列的unsigned char, 值从0~ 255 ，放在 u_char data_array[ARRAY_SIZE] 中，分配一个数组 int membuffer[256]; 用于统计每个元素出现的次数，也就成为了数组的排序结果。

1 for(int i=0;i<256;i++) 
2   membuffer[i]=0; 
3 for(int i=0;i<ARRAY_SIZE;i++) 
4   membuffer[data_array[i]]++;

1.2 基数排序分析

基数排序的优点就是：不用比较，每个关键字的范围确定且一般较小，排序时间复杂度低。但为什么基数排序的应用范围没有快速排序那样广呢？原因有以下几点：

1）基数排序一般需要额外的存储空间：顺序队列实现需要O(n)的元素空间，链队列实现需要O(n+2d)个指针空间，计数实现也需要O(n)的元素空间

2）基数排序的时间复杂度看似O(n)，但它每次排序都是对整个数组的处理，相对快排来讲，cache局部性不好。

在我的印象中，基数排序一般出现在面试中，在实际生产环境中还没有发现采用基数排序。

2. 基数排序代码

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 
 5 // 基于无符号整数的基数排序
 6 void radix(int byte, unsigned int N, const unsigned int *source, unsigned int *dest) {
 7   unsigned int count[256];
 8   unsigned int index[256];
 9   int i = 0;
10 
11   memset(count, 0, sizeof (count));
12 
13   // 统计出现频率
14   for (i=0; i < N; ++i) {
15     ++count[((source[i])>>(byte*8))&0xff]; // 以一个字节为单位
16   }
17 
18   // 为dest下标初始化做准备
19   index[0] = 0;
20   for (i = 1; i < 256; ++i) {
21     index[i] = index[i-1] + count[i-1];
22   }
23 
24   // 数组重排列
25   for (i = 0; i < N; ++i) {
26     dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
27   }
28 }
29 
30 void radixsort (unsigned int *source, unsigned int *temp, unsigned int N) {
31   radix(0, N, source, temp);
32   radix(1, N, temp, source);
33   radix(2, N, source, temp);
34   radix(3, N, temp, source);
35 }
36 
37 
38 int main(int argc, char** argv) {
39   unsigned int a[5] = {300, 200, 2,20, 5};
40   unsigned int len = 5;
41   unsigned int b[5] = {0};
42   unsigned int i = 0;
43 
44   radixsort(a, b, len);
45   for (; i < 5; ++i) {
46     printf("%ld ", a[i]);
47   }
48 
49   return 0;
50 }

3. 基数排序测试

1）上节代码的运行结果如下：

2）网友的性能对比测试：

引用网络上的测试数据：

今实测性能在n =1024*1000的时候，VC 6 上 release 模式，排序时间：(tick)

n Radix Sort STL Sort
100*1024 20 20
1000*1024 250 320
4000*1024 991 1513
10000*1024 2093 3606

从以上数据可见Radix Sort 的确可能比STL Sort 快，而且，因为Radix Sort时间复杂度小，在更长的时间内表现更为充分。n 从100* 1024增长到10000*1024，排序时间也从20 增长到2093，可以看出的确是O(n)的。

4. 小结

基数排序采用多关键字的排序思想，由最低位到最高位逐步处理各关键字断序列，达到了O(n)的时间复杂度，但增加了空间复杂度。

基数排序一般适用于已知关键字的分布情况，且分布比较集中。计算机实现一般采用分配-收集策略或计数方式（统计各关键字的出现频率）。

5. 参考资料

Radix Sort 的介绍