首页 > 代码库 > 数据结构——基数排序
数据结构——基数排序
排序过程
以数组 A[6]={23, 14, 101, 72, 84, 11}为例,调用基数排序过程如下图所示:
基本思想是:将整数按位切割成不同的数字,然后对每个数的同一位进行排序。
具体做法:将所有待排序数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序操作。这样从最低位排序一直到最高位排序完毕,数组就变成一个有序数组了。
源码实现
private static void sort(int[] A) { int mod = 1; // 位数 int bit = 4; // 数组中值最大为4位数 int[][] tempPlace = new int[10][A.length]; // 建造一个大小为10桶。一维为元素的某一位的值,二维为元素的值 for (int z = 1;z <= bit;z++) { // 循环数组中最大值的位数 int[] temp = new int[10]; // 保存每个tempPlace桶的当前下标 for (int i = 0,j = 0;i < A.length;i++,j++) { int k = A[i]/mod % 10; tempPlace[k][temp[k]] = A[i]; temp[k]++; } int length = 0; for (int i = 0;length<A.length;i++) { for (int j = 0;j < temp[i];j++) { A[length++] = tempPlace[i][j]; } } mod*=10; }}
参考资料
[1] 基数排序
[2] 算法导论, 8.3 - 基数排序
数据结构——基数排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。