首页 > 代码库 > 基数排序

基数排序

基本解法

第一步

以LSD为例,假设原来有一串数值如下所示:
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中:
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39

第二步

接下来将这些桶子中的数值重新串接起来,成为以下的数列:
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配,这次是根据十位数来分配:
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93

第三步

接下来将这些桶子中的数值重新串接起来,成为以下的数列:
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为止。
LSD的基数排序适用于位数小的数列,如果位数多的话,使用MSD的效率会比较好。MSD的方式与LSD相反,是由高位数为基底开始进行分配,但在分配之后并不马上合并回一个数组中,而是在每个“桶子”中建立“子桶”,将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

实现方法

最高位优先(Most Significant Digit first)法,简称MSD法:先按k1排序分组,同一组中记录,关键码k1相等,再对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd对各子组排序后。再将各组连接起来,便得到一个有序序列。
最低位优先(Least Significant Digit first)法,简称LSD法:先从kd开始排序,再对kd-1进行排序,依次重复,直到对k1排序后便得到一个有序序列。

实现原理

基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。它是这样实现的:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。

代码

 1 int maxbit(int data[], int n) //辅助函数,求数据的最大位数 2 { 3     int d = 1; //保存最大的位数 4     int p = 10; 5     for(int i = 0; i < n; ++i) 6     { 7         while(data[i] >= p) 8         { 9             p *= 10;10             ++d;11         }12     }13     return d;14 }15 void radixsort(int data[], int n) //基数排序16 {17     int d = maxbit(data, n);18     int *tmp = newint[n];19     int *count = newint[10]; //计数器20     int i, j, k;21     int radix = 1;22     for(i = 1; i <= d; i++) //进行d次排序23     {24         for(j = 0; j < 10; j++)25             count[j] = 0; //每次分配前清空计数器26         for(j = 0; j < n; j++)27         {28             k = (data[j] / radix) % 10; //统计每个桶中的记录数29             count[k]++;30         }31         for(j = 1; j < 10; j++)32             count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶33         for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中34         {35             k = (data[j] / radix) % 10;36             tmp[count[k] - 1] = data[j];37             count[k]--;38         }39         for(j = 0; j < n; j++) //将临时数组的内容复制到data中40             data[j] = tmp[j];41         radix = radix * 10;42     }43     delete[]tmp;44     delete[]count;45 }

 

基数排序