概念：
基数排序属于“分配式排序”，又称“桶子法”，顾名思义，它是透过键值的部分资讯，将要排序的元素分配至某些“桶”中，即以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
实现方法：
最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便起到一个有序序列。
最低位优先(Least Significance Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。
实现原理：
基数排序的发明可以追溯导1887年，赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。它是这样实现的：将所有待比较数值(正整数)统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序的方式可以采用LSD(Least significance digital)或MSD(Most significance digital)，LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
示例：
package com.cnblogs.lxj.testarraysort;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @packageName: com.cnblogs.lxj.testarraysort
* @className: RadixSort
* @description: 测试基数排序
* @author: liuxiaojiang
* @date: 2021/1/8
*/
public class RadixSort {
public static void main(String[] args) {
int[] a = new int[]{321,1,10,60,577,743,127};
printArray(a);
radixSortOne(a,10,3);
printArray(a);
}
/**
* @description: 基数排序方法(1)
* @author: liuxiaojiang
* @date: 2021/1/8
* @param a: 代表数组
* @param radix: 代表基数
* @param d: 代表排序元素的位数
* @return: void
**/
public static void radixSortOne(int[] a,int radix,int d){
List<List<Integer>> ts = new ArrayList<List<Integer>>();
int rate = 1;
for(int i = 0;i < radix;i++){
List<Integer> t = new ArrayList<Integer>();
ts.add(t);
}
for(int i = 0;i < d;i++){
for(int j = 0;j < radix;j++){
List<Integer> t = ts.get(j);
t.clear();
}
for(int j = 0;j < a.length;j++){
int subKey = (a[j]/rate) % radix;
List<Integer> t = ts.get(subKey);
t.add(a[j]);
}
int count = 0;
for(int j = 0; j < radix;j++){
List<Integer> t = ts.get(j);
for(int k = 0;k < t.size();k++){
a[count++] = t.get(k);
}
}
rate *= radix;
System.out.print("第"+(i+1)+"次：");
printArray(a);
}
}
/**
* @description: 基数排序方法(2)
* @author: liuxiaojiang
* @date: 2021/1/8
* @param array: 代表数组
* @param radix: 代表基数
* @param d: 代表排序元素的位数
* @return: void
**/
public static void radixSortTwo(int[] array,int radix,int d){
int[] tempArray = new int[array.length];
int[] count = new int[radix];
int rate = 1;
for(int i = 0;i < d;i++){
Arrays.fill(count,0);
System.arraycopy(array,0,tempArray,0,array.length);
for(int j = 0;j < array.length;j++){
int subKey = (tempArray[j] / rate) % radix;
count[subKey]++;
}
for(int j = 1;j < radix;j++){
count[j] = count[j] + count[j - 1];
}
for(int m = array.length - 1;m >= 0;m--){
int subKey = (tempArray[m] / rate) % radix;
array[--count[subKey]] = tempArray[m];
}
rate *= radix;
System.out.print("第"+(i+1)+"次：");
printArray(array);
}
}
/**
* @description: 输出方法
* @author: liuxiaojiang
* @date: 2021/1/8
* @param array: 代表数组
* @return: void
**/
public static void printArray(int[] array){
for(int i : array){
System.out.print(i+" ");
}
System.out.println();
}
}
运行结果：
321 1 10 60 577 743 127 //初始化
第1次：10 60 321 1 743 577 127
第2次：1 10 321 127 743 60 577
第3次：1 10 60 127 321 577 743
1 10 60 127 321 577 743 //最终结果
原理：
