1. 简单介绍
- 将整数按位数切割成不同的数字，然后按每个位数分别比较；本质上是一种多关键字排序；
- 基数排序(Radix Sort) 属于“分配式排序”，又称“桶子法”。顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用；
- 基数排序法是属于稳定的排序，基数排序法的是效率高的稳定性排序法；
- 基数排序是桶排序的扩展。
2. 基本思想
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序 ... 这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
举例说明：
- 第 1 轮排序
- 第 2 轮排序
- 第 3 轮排序
标配
- 平均时间复杂度：O(n+k)
- 最坏时间复杂度：O(n^2)
- 最好时间复杂度：O(n)
- 空间复杂度：O(n+k)
- 稳定
3. 标配
- 平均时间复杂度：O(n+k)
- 最坏时间复杂度：O(n^2)
- 最好时间复杂度：O(n)
- 空间复杂度：O(n+k)
- 稳定
4. 代码实现
import java.util.Arrays;
public class RadixSort {
public static void main(String[] args) {
// int[] arr = {53, 3, 542, 748, 14, 214};
int[] arr = {421, 240, 115, 532, 305, 430, 124};
sort_2(arr);
System.out.println(Arrays.toString(arr));
}
// 基数排序 → k 次计数排序
public static void sort_2(int[] arr) {
// 1. 本数组中最大值的位数
int max = arr[0];
for (int i = 1; i < arr.length; i++)
max = Math.max(max, arr[i]);
int maxLength = (max+"").length();
// 2. 存放中间结果的数组
int[] temp = new int[arr.length];
// 3. 以关键词 digit 进行计数排序
for (int k = 0, division = 1; k < maxLength; k++, division*= 10) {
int digit;
// a. 计数数组
int[] count = new int[10];
for (int i = 0; i < arr.length; i++) {
digit = arr[i] / division % 10;
count[digit]++;
}
// b. 累加数组
for (int i = 1; i < count.length; i++)
count[i] = count[i] + count[i-1];
// c. 反向遍历原始数组, 将结果放入 temp
for (int i = arr.length-1; i >= 0; i--) {
digit = arr[i] / division % 10;
temp[--count[digit]] = arr[i];
}
// d. 将结果放回原始数组
System.arraycopy(temp, 0, arr, 0, arr.length);
// e. 清空累加数组, 以便下轮使用
Arrays.fill(count, 0);
}
}
// 实实在在的桶：二维数组，空间复杂度高达 O(10*n)
public static void sort_1(int[] arr) {
// 1. 本数组中最大值的位数
int max = arr[0];
for (int i = 1; i < arr.length; i++)
max = Math.max(max, arr[i]);
int maxLength = (max+"").length();
// 2. 建桶
int[][] buckets = new int[10][arr.length];
int[] bucketEleCounts = new int[10];
// 3. 排序
int index, digit;
for (int k = 0, division = 1; k < maxLength; k++, division*=10) {
// a. 根据关键字(ge/shi/bai) 将元素放入对应的桶
for (int j = 0; j < arr.length; j++) {
digit = arr[j] / division % 10;
buckets[digit][bucketEleCounts[digit]++] = arr[j];
}
// b. 将桶中的数据再放回原数组
index = 0;
for (int i = 0; i < buckets.length; i++)
for (int j = 0; j < bucketEleCounts[i]; j++)
arr[index++] = buckets[i][j];
// c. 清空 bucketEleCounts, 以便下一轮重新计数
for (int i = 0; i < bucketEleCounts.length; i++)
bucketEleCounts[i] = 0;
}
}
}
5. summary
- 本质上是一种多关键字排序
- 分成【低位优先】和【高位优先】两种
- LSD(Least Significant Digit first)：下面的代码实现都是该方法
- MSD：以最高位为关键字分别将数据放入各个桶，再在桶内部再按照原数据次高位来排 ...
- 基数排序是对传统桶排序的扩展，速度很快。
- sort_1 实现的基数排序是经典的空间换时间的方式，占用内存很大；当对海量数据排序时，容易造成 OutOfMemoryError。
- 有负数的数组，我们不用基数排序来进行排序 ( 并不是说不支持负数）。
6. 桶 | 计数 | 基数
