5分钟了解基数排序
前言
基数排序无需进行比较和交换，而是利用分配和收集两种基本操作实现排序。基数排序分为两种：第一种是LSD ，从最低位开始排序；第二种是 MSD， 从最高位开始排序。
。
基数排序思想介绍
分配：对于数字，每位的取值范围是0-9，因此需要10个容器（我们可以将其称为桶），这10个桶标号为0-9。每趟排序时，我们取每一个元素在该位的数值依次放入桶中。
2. 收集：在一趟排序完成后，我们按顺序从0-9的桶中依次取元素。
3. 继续进行分配和收集，直到最大位数排序完成。
算法说明：
待排序数据：12, 34, 2, 123, 25, 59, 37
采用LSD，从低位开始排序
第一轮：取个位数，放入对应的桶，比如12的个位数是2，放到2号桶；34的个位数是4，放到4号桶
0
1
2122
3123
434
525
6
737
8
959
第一轮后，得到数据：12, 2, 123, 34, 25, 37, 59
第二轮：取十位数，放入桶中。比如2，十位数是0，放到0号桶
02
112123
225
33437
4
559
6
7
8
9
第二轮后，得到数据：2, 12, 123, 25, 34, 37, 59
第三轮：取百位数，放入桶
021225343759
1123
2
3
4
5
6
7
8
9
最后，得到有序数据 2, 12, 25, 34, 37, 59, 123
基数排序的代码实现
private static void radixSort(int[] arr) {
//存储最大值，暂时记录为第一个元素
int max = arr[0];
//获取待排序数组中的最大值
for (int v : arr) {
if (v > max) {
max = v;
}
}
// 用列表表示桶，一共10个桶，每个桶对应的元素也是列表
List<List<Integer>> list = new ArrayList<List<Integer>>();
for(int i = 0; i < 10; i ++) {
list.add(new ArrayList<Integer>());
}
// 确定循环轮数
for(int i = 0, factor = 1; i < max; factor *= 10, i ++) {
for(int j = 0; j < arr.length; j ++) {
// 根据相应的位（个位/十位...）取通号，然后将数据放入桶中
list.get((arr[j] / factor) % 10).add(arr[j]);
}
// 遍历桶，将其中数据放入arr数组中
for(int j = 0, k = 0; j < list.size(); j ++) {
while(!list.get(j).isEmpty()) {
arr[k] = list.get(j).get(0);
list.get(j).remove(0);
k++;
}
}
}
}
总结
基数排序是一种按记录关键字的各位值逐步进行排序的方法。一般适用于记录的关键字为整数类型的情况，对于字符串和文字排序不适合。
网友评论