一、排序思想基数排序是桶排序的扩展，它将所有待排序的数值统一为同样的数位长度，数位较短的前面补0，然后从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成后，待排序列就有序了。 1. 案例： 现有如下待排序列： 53 3 542 748 14 214
然后假如有如下10个桶(一维数组)，编号从0到9：  桶- 第一轮排序：将每个元素的个位数取出，然后放到对应编号的桶里。比如第一个元素
53，个位数是3，所以放在下标为3的桶里。一轮下来，情况如下：
 第一轮第一轮结束后，按照桶下标顺序，依次取出各桶中数据，放回原数组，所以原数组就变成了： 542 53 3 14 214 748
- 第二轮：将每个元素的十位取出(没有十位的就是0)，然后放到对应编号的桶里。比如第一个元素
542，十位是4，所以放到下标为4的桶里。一轮下来，情况如下：
 第二轮第二轮结束后，按照桶下标顺序，依次取出桶中数据，放回原数组，所以原数组就变成了： 3 14 214 542 748 53
- 第三轮：将每个元素的百位取出(没有百位的就是0)，然后放到对应编号的桶里。比如第一个元素
3，百位是0，所以放到下标为0的桶里。一轮下来，情况如下：
 第三轮第三轮结束后，按照桶下标顺序，依次取出桶中数据，放回原数组，所以原数组就变成了： 3 14 53 214 542 748
此时数组就是有序的了。总共要进行几轮呢？就是数组中最大数有多少位，就要进行几轮。通过这些分析大家发现啥没有？每一轮的排序，就是对0到9数字排序，那岂不是很适合用计数排序？没错，就是这样，所以，基数排序中，我们要做的就是每一轮都用计数排序就好了。 二、代码实现以下代码就是基于计数排序实现的，网上的一些基数排序教程可能会用二维数组来表示桶，这样容易理解，但是非常浪费空间。 public static void radixSort(int[] arr) {
if (arr == null || arr.length == 1) {
return;
}
// 1. 先求数组中最大数的位数
int max = arr[0];
for(int i=1; i<arr.length; i++) {
max = arr[i] > max ? arr[i] : max;
}
int maxLength = (max + "").length();
// 2. 定义一个用来接收每一轮排序结果的数组
int[] result = new int[arr.length];
// 3. 定义一个长度为数据范围的数组，每个数各数位只可能是0到9，所以数组长度为10
int[] count = new int[10];
// 4. 循环进行排序
for(int i=0; i<maxLength; i++) {
// 5. 第一轮求个位，第二轮求十位……，求个位：num / 1 % 10，求百位：num / 10 % 10……
int division = (int)Math.pow(10, i); // 求10的次方
// 从这里开始其实就是计数排序
for(int j=0; j<arr.length; j++) {
int num = arr[j] / division % 10;
// num就是数组下标值，然后该下标对应的元素值加1。count数组下标和对应的值就表示该数出现了多少次
count[num] ++;
}
// 6. 对count进行变形，使其变成稳定的
for(int x=1; x<count.length; x++) {
count[x] += count[x-1];
}
// 7. 逆序遍历原数组
for(int y=arr.length-1; y>=0; y--) {
int num = arr[y] / division % 10;
result[count[num] - 1] = arr[y];
count[num]--;
}
// 8. 拷贝result到原数组
System.arraycopy(result, 0, arr, 0, arr.length);
// 9. 清空count，进行下一轮的计数
Arrays.fill(count, 0);
}
}
|
