基数排序（RadixSort）是桶排序的升级版，属于分配式排序。它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序示意图
在这个过程中创建桶进行辅助排序
桶
特点
速度快
空间换时间，排序速度快
空间浪费巨大
因为排序基于桶，桶需要占据大量空间，一个长度为 length 的数组，它的桶就是一个 [10][length] 的二维数组（如果算上负数，那就需要 [19][length] 的二维数组）
不适合负数排序
因为桶是二维数组，第一维度代表的是每一位的数值，如果有负数会报错（如： new int[-10]），需要进行改造
java 实现：
public class RadixSortTest {
public static void main(String[] args) {
int[] input = {2,5,4,89,20,89,6,0,54,78,2};
radixSort(input);
PrintUtils.print(input);
}
public static void radixSort(int[] arr) {
//桶
int[][] bucket = new int[10][arr.length];
//统计每个桶的有效元素个数
int[] bucketCounter = new int[10];
//位数
int place = 0;
int max = 0;
for (int n = 0; n < arr.length; n++){
if (arr[n] > max){
max = arr[n];
}
}
int maxLength = (max + "").length();
for (int m = 0; m < maxLength; m++){
//按位数，依次存入对应的桶中
for (int i = 0; i < arr.length; i++){
int placeValue = arr[i] / (int)Math.pow(10, place) % 10;
bucket[placeValue][bucketCounter[placeValue]++] = arr[i];
}
place++;
//从桶中取出，依次放回 arr
int returnPointer = 0;
for (int j = 0; j < 10; j++){
int[] placeArr = bucket[j];
for (int k = 0; k < bucketCounter[j]; k++){
arr[returnPointer++] = placeArr[k];
}
//还原 bucketCounter
bucketCounter[j] = 0;
}
}
}
}
时间复杂度
- 最优时间复杂度：O(d(n+r))
- 最坏时间复杂度：O(d(n+r))
- 稳定性：稳定
