时间:2021-05-20
算法思想:依次按个位、十位...来排序,每一个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语言实现基数排序代码分享的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他Java相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了Python实现的基数排序算法。分享给大家供大家参考,具体如下:基数排序(radixsort)属于“分配式排序”(distributionsort
本文实例讲述了JS使用队列对数组排列,基数排序算法。分享给大家供大家参考,具体如下:/**使用队列对数组排列,基数排序*对于0~99的数字,基数排序将数组集扫描
C语言中数据结构之链式基数排序实现效果图:实例代码:#include#include#include#defineTRUE1#defineFALSE0#defi
本文实例讲述了PHP实现基数排序的方法。分享给大家供大家参考,具体如下:基数排序是根据关键字中各位的值,通过对排序的N个元素进行若干趟“分配”与“收集”来实现排
这篇文章主要介绍了Java如何实现八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序、快速排序、归并排序、堆排序和LST基数排序,分享给大家一起学习。分