社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
基本思想
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
基数排序可以采用两种方式：
我们以LSD方式为例，从数组R[1..n]中每个元素的最低位开始处理，假设基数为radix，如果是十进制，则radix=10。基本过程如下所示：
算法实现
基数排序算法，Java实现，代码如下所示：
01 |
public abstract class Sorter {
|
02 |
public abstract void sort(int[] array);
|
03 |
} |
04 |
05 |
public class RadixSorter extends Sorter {
|
06 |
|
07 |
private int radix;
|
08 |
|
09 |
public RadixSorter() {
|
10 |
radix = 10;
|
11 |
}
|
12 |
|
13 |
@Override
|
14 |
public void sort(int[] array) {
|
15 |
// 数组的第一维表示可能的余数0-radix，第二维表示array中的等于该余数的元素
|
16 |
// 如：十进制123的个位为3，则bucket[3][] = {123}
|
17 |
int[][] bucket = new int[radix][array.length];
|
18 |
int distance = getDistance(array); // 表示最大的数有多少位
|
19 |
int temp = 1;
|
20 |
int round = 1; // 控制键值排序依据在哪一位
|
21 |
while (round <= distance) {
|
22 |
// 用来计数：数组counter[i]用来表示该位是i的数的个数
|
23 |
int[] counter = new int[radix];
|
24 |
// 将array中元素分布填充到bucket中，并进行计数
|
|
版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。 原文链接：https://blog.csdn.net/weixin_33739627/article/details/90654695 站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。
官方社群 |
