JAVA十大排序算法之基数排序详解

JAVA十大排序算法之基数排序详解

目录基数排序代码实现时间复杂度算法稳定性基数排序 vs 桶排序 vs 计数排序总结

基数排序

常见的数据元素一般是由若干位组成的，比如字符串由若干字符组成，整数由若干位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;

maxDigit++;

}

//创建桶并初始化

ArrayList> 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 list = bucket.get(k);

for (int m = 0http://; 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));

}

}

时间复杂度

计数排序算法的时间复杂度是O(N+M)，基数排序算法执行了k次计数排序，所mWjGNzF以基数排序算法的时间复杂度为O(K(N+M))。

算法稳定性

从上面的分析可以看出，相同元素会按照顺序放进固定的桶内，取出的时候也是按照顺序取出来的，所以基数排序算法是一种稳定的排序算法。

基数排序 vs 桶排序 vs 计数排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异

基数排序：根据每一位的关键字来分配桶

桶排序：存储一定范围的值

mWjGNzF 计数排序：每个桶只存储一个类型值，但是数量不限

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容!

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。