1、基数排序介绍
基数排序（radix sort）属于 “分配式排序” (distribution sort)，又称为 “桶子法”（bucket sort），或者 bin sort，它通过把要排序的元素分配到一些桶中，进行排序。
基数排序属于稳定的排序，基数排序是效率比较高的排序法。基数排序是桶排序的扩展
基数排序主要利用分配和收集两种基本操作，不太适合对字符串和文字等进行排序。
2、基数排序基本思想
- 将所有待比较的值统一为同样的数位长度，数位短的前面 补零，然后从低位开始依次进行排序，从最低位到最高位排序完成后数列就变为有序数列
- 基数排序从低位到高位进行，使最后一次计数排序完成后，数组有序，原理在于对待排序的数据，权重未知的情况
- 先按照权重小的因子排序，然后按照权重大的因子排序，所以基数排序更适合对时间、字符串等这些权重未知的数据进行排序
3、基数排序代码实现
分步代码实现
public static void main(String[] args) {
int[] arr = {
23, 2, 12, 54, 829, 45, 78, 767};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr) {
// 第一轮排序对每个元素的个位进行排序
// 定义一个二维数组，表示从 0 到 9 这 10 个桶，每个桶是一个一位数组。每个一位数组大小定为 arr.length
int[][] bucket = new int[10][arr.length];
// 定义个一个一维数组，记录每个桶（也就是 0 ~ 9 这几个桶）存放数据的个数
int[] bucketElementCounts = new int[10];
// 第一次循环，先比较个位数
for (int i = 0; i < arr.length; i++) {
// 取出每个元素的个位
int digitOfElement = arr[i] % 10;
// 取出的个位放到对应的桶中。比如数组中第 1 元素 23 取出个位 3 应该放到二维数组 bucket[3][bucketElementCounts[3]] 的位置
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i];
bucketElementCounts[digitOfElement]++;
}
int index = 0;
// 比较完个位数后重新存入原数组
for (int i = 0; i < bucketElementCounts.length; i++) {
// 如果桶中有数据，放进原数组中
if (bucketElementCounts[i] != 0) {
// 循环第 i 个桶中的数据
for (int j = 0; j < bucketElementCounts[i]; j++) {
// 赋值到原数组
arr[index++] = bucket[i][j];
}
}
// 处理完成后将桶中个数置为 0
bucketElementCounts[i] = 0;
}
// 第一次循环结果：[2, 12, 23, 54, 45, 767, 78, 829]
// 第二次循环，比较十位数
for (int i = 0; i < arr.length; i++) {
// 取出每个元素的十位
int digitOfElement = arr[i] / 10 % 10;
// 取出的十位放到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i];
bucketElementCounts[digitOfElement]++;
}
index = 0;
// 比较完十位数后重新存入原数组
for (int i = 0; i < bucketElementCounts.length; i++) {
// 如果桶中有数据，放进原数组中
if (bucketElementCounts[i] != 0) {
// 循环第 i 个桶中的数据
for (int j = 0; j < bucketElementCounts[i]; j++) {
// 赋值到原数组
arr[index++] = bucket[i][j];
}
bucketElementCounts[i] = 0;
}
}
// 第二次循环结果：[2, 12, 23, 829, 45, 54, 767, 78]
// 第三次循环，比较百位数
for (int i = 0; i < arr.length; i++) {
// 取出每个元素的百位
int digitOfElement = arr[i] / 100 % 10;
// 取出的百位放到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i];
bucketElementCounts[digitOfElement]++;
}
index = 0;
// 比较完百位数后重新存入原数组
for (int i = 0; i < bucketElementCounts.length; i++) {
// 如果桶中有数据，放进原数组中
if (bucketElementCounts[i] != 0) {
// 循环第 i 个桶中的数据
for (int j = 0; j < bucketElementCounts[i]; j++) {
// 赋值到原数组
arr[index++] = bucket[i][j];
}
}
}
// 第三次排序结果：[2, 12, 23, 45, 54, 78, 767, 829] 成为有序数列
}
完整代码实现
public static void main(String[] args) {
int[] arr = {
23, 2, 12, 54, 829, 45, 78, 767};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr) {
// 首先循环取得数组中最大数
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 最大数是几位数
int maxLength = (max + "").length();
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
// 创建桶，总共 10 个桶，每个桶最多 arr.length 个数
int[][] bucket = new int[10][arr.length];
// 记录每个桶中的数据
int[] bucketElementCounts = new int[10];
// 遍历数组
for (int j = 0; j < arr.length; j++) {
int digitOfElement = arr[j] / n % 10;
// 比较后放到 bucket 中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
int index = 0;
for (int j = 0; j < bucketElementCounts.length; j++) {
if (bucketElementCounts[j] != 0) {
for (int k = 0; k < bucketElementCounts[j]; k++) {
// 赋值到原数组
arr[index++] = bucket[j][k];
}
}
bucketElementCounts[j] = 0;
}
System.out.printf("第%s轮循环的结果为：%s\n", i + 1, Arrays.toString(arr));
}
}