基数排序Java版
题目和我的前几个排序一样
这次是Java版的
代码 + 注释
package com.vdian.qatest.supertagbiz.test.niu;
/**
* Created by fengyanhua on 2019/6/28.
*/
public class sortJiSu {
public static void main(String[] args) {
int[] arrays = {73,22,93,43,55,14,28,65,39,81};
radixSort(arrays);
System.out.println("arrays:" + arrays);
}
public static void radixSort(int[] arrays) {
int max = findMax(arrays, 0, arrays.length - 1);
//需要遍历的次数由数组最大值的位数来决定
for (int i = 1; max / i > 0; i = i * 10) {
int[][] buckets = new int[arrays.length][10];
//获取每一位数字(个、十、百、千位...分配到桶子里)
for (int j = 0; j < arrays.length; j++) {
int num = (arrays[j] / i) % 10;
//将其放入桶子里
buckets[j][num] = arrays[j];
}
//回收桶子里的元素
int k = 0;
//有10个桶子
for (int j = 0; j < 10; j++) {
//对每个桶子里的元素进行回收
for (int l = 0; l < arrays.length ; l++) {
//如果桶子里面有元素就回收(数据初始化会为0)
if (buckets[l][j] != 0) {
arrays[k++] = buckets[l][j];
}
}
}
}
}
/**
* 递归，找出数组最大的值
*
* @param arrays 数组
* @param L 左边界，第一个数
* @param R 右边界，数组的长度
* @return
*/
public static int findMax(int[] arrays, int L, int R) {
//如果该数组只有一个数，那么最大的就是该数组第一个值了
if (L == R) {
return arrays[L];
} else {
int a = arrays[L];
int b = findMax(arrays, L + 1, R);//找出整体的最大值
if (a > b) {
return a;
} else {
return b;
}
}
}
}
思路
假设原来有一串数值如下所示：
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
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
总结
基数排序没有关键字的比较，通过"分配"和"收集"过程来实现排序
排序过程中，要注意"分配"和"收集"的顺序（重点）
概念
基数排序是一种借助于多关键字排序的思想对单关键字排序的方法，是通过"分配"和"收集"的过程来实现排序.
参考链接:
[https://v.youku.com/v_show/id_XMTYxNjYzNjYwNA==.html?spm=a2h0k.11417342.soresults.dtitle]