基数排序
常见的数据元素一般是由若干位组成的，比如字符串由若干字符组成，整数由若干位0~9数字组成。
基数排序按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，同时每一轮排序都基于上轮排序后的结果；当我们将所有的位排序后，整个数组就达到有序状态。基数排序不是基于比较的算法。
基数是什么意思？对于十进制整数，每一位都只可能是0~9中的某一个，总共10种可能。那10就是它的基，同理二进制数字的基为2；对于字符串，如果它使用的是8位的扩展ASCII字符集，那么它的基就是256。
基数排序有两种方法：
- MSD 从高位开始进行排序
- LSD 从低位开始进行排序
对于大小范围为0~9的数的组合（若是两位数，就是个位数和十位数的组合），于是可以准备十个桶，然后放到对应的桶里，然后再把桶里的数按照0号桶到9号桶的顺序取出来即可。
代码实现
public class RadixSort {
public static final int[] ARRAY = {82, 50, 21, 5, 66, 48, 43, 79, 14, 37, 25};
public static int[] sort(int[] array) {
if (array.length < 2) return array;
//根据最大值算出位数
int max = array[0];
for (int temp : array) {
if (temp > max) {
max = temp;
}
}
//算出位数digit
int maxDigit = 0;
while (max != 0) {
max /= 10;
<b>本文来源gao@!dai!ma.com搞$$代^@码5网@</b> maxDigit++;
}
//创建桶并初始化
ArrayList<ArrayList<Integer>> bucket = new ArrayList<>();
for (int i = 0; i < 10; i++) {
bucket.add(new ArrayList<>());
}
//按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，每一轮排序都基于上轮排序后的结果
int mold = 10;//取模运算
int div = 1;//获取对应位数的值
for (int i = 0; i < maxDigit; i++, mold *= 10, div *= 10) {
for (int j = 0; j < array.length; j++) {
//获取个位/十位/百位......
int num = (array[j] % mold) / div;
//把数据放入到对应的桶里
bucket.get(num).add(array[j]);
}
//把桶中的数据重新写回去，并把桶的元素清空，开始第二轮排序
int index = 0;
for (int k = 0; k < bucket.size(); k++) {
//桶中对应的数据
ArrayList<Integer> list = bucket.get(k);
for (int m = 0; m < list.size(); m++) {
array[index++] = list.get(m);
}
//清除桶
bucket.get(k).clear();
}
}
return array;
}
public static void print(int[] array) {
for (int i : array) {
System.out.print(i + " ");
}
System.out.println("");
}
public static void main(String[] args) {
print(ARRAY);
System.out.println("============================================");
print(sort(ARRAY));
}
}
时间复杂度
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：JAVA十大排序算法之基数排序详解
转载请注明原文链接：JAVA十大排序算法之基数排序详解
