首页 > 代码库 > 数据结构——基数排序

数据结构——基数排序

排序过程

以数组 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 - 基数排序

数据结构——基数排序