13518219792
这篇文章主要介绍Java语言怎么实现基数排序，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！
站在用户的角度思考问题，与客户深入沟通，找到辉南网站设计与辉南网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：网站设计制作、成都做网站、企业官网、英文网站、手机端网站、网站推广、域名申请、虚拟主机、企业邮箱。业务覆盖辉南地区。
算法思想：依次按个位、十位...来排序，每一个pos都有分配过程和收集过程，array[i][0]记录第i行数据的个数。
package sorting;
/**
* 基数排序
* 平均O(d(n+r)),最好O(d(n+r)),最坏O(d(n+r));空间复杂度O(n+r);稳定;较复杂
* d为位数,r为分配后链表的个数
* @author zeng
*
*/
public class RadixSort {
//pos=1表示个位，pos=2表示十位
public static int getNumInPos(int num, int pos) {
int tmp = 1;
for (int i = 0; i < pos - 1; i++) {
tmp *= 10;
}
return (num / tmp) % 10;
}
//求得最大位数d
public static int getMaxWeishu(int[] a) {
int max = a[0];
for (int i = 0; i < a.length; i++) {
if (a[i] > max)
max = a[i];
}
int tmp = 1, d = 1;
while (true) {
tmp *= 10;
if (max / tmp != 0) {
d++;
} else
break;
}
return d;
}
public static void radixSort(int[] a, int d) {
int[][] array = new int[10][a.length + 1];
for (int i = 0; i < 10; i++) {
array[i][0] = 0;
// array[i][0]记录第i行数据的个数
}
for (int pos = 1; pos <= d; pos++) {
for (int i = 0; i < a.length; i++) {
// 分配过程
int row = getNumInPos(a[i], pos);
int col = ++array[row][0];
array[row][col] = a[i];
}
for (int row = 0, i = 0; row < 10; row++) {
// 收集过程
for (int col = 1; col <= array[row][0]; col++) {
a[i++] = array[row][col];
}
array[row][0] = 0;
// 复位，下一个pos时还需使用
}
}
}
public static void main(String[] args) {
int[] a = { 49, 38, 65, 197, 76, 213, 27, 50 };
radixSort(a, getMaxWeishu(a));
for (int i : a)
System.out.print(i + " ");
}
}关注一下运行结果：
以上是“Java语言怎么实现基数排序”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注创新互联行业资讯频道！
