首页 > 代码库 > 基数排序
基数排序
基本解法
第一步
以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 }
基数排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。