基数排序介绍

基数排序，是一种非比较型整数排序算法，先把所有元素补位，让所有元素的位数相同，然后把序列中的每个元素按照位数进行分桶的一种算法，

基数排序的实现方法分为两种：MSD和LSD。

MSD：最高位优先法（Most Significant Digit First），先比较最高位，最高位分到一个桶中的，再按照第二位进行分桶…，知道分到最后一位，然后再从最小的桶中逐层向上，把元素都拿出来，即完成排序。

LSD：最低位优先法（Least Significant Digit First），先比较最低位，也就是个位，进行分桶，分桶过程中分到一个桶中的数据直接追加到桶中即可，无需排序。然后将所有同种的元素按桶的顺序拿出，重新组成序列，然后比较十位，进行分桶…直到比较到最高位，重新组成序列即可完成排序。

基数排序步骤

以LSD为例

设定10个桶，分别存放位数为0-9的元素。遍历初始序列，将元素放入不同的桶中按照桶的顺序，把桶中元素全部拿出来重新组装成一个序列。重复2、3步骤，直到最高位。即可完成排序代码实现

public class RadixSort {	public static void radixSort(int[] arr) {		if (arr == null || arr.length == 0) {			return;		}		// 采用LSD方法		radixSortLSD(arr, 1);	}	/**	 * LSD方式 排序	 * @param arr 序列	 * @param digit 位数 个位1十位2百位3......	 */	private static void radixSortLSD(int[] arr, int digit) {		int len = arr.length;		// 定义十个桶（分别存放个位数为0、1、2......9的数字）		int[][] buckets = new int[10][];		boolean isAppend = false;		for (int i = 0; i < len; i++) {			String valStr = String.valueOf(arr[i]);			if (valStr.length() >= digit) {				int index =  Integer.parseInt(valStr.substring(valStr.length() - digit, valStr.length() - digit + 1));				buckets[index] = appendItem(buckets[index], arr[i]);				isAppend = true;			}		}		// 从桶中拿出所有元素		if (isAppend) {			int k = 0;			for (int[] b : buckets) {				if (b != null) {					for (int i = 0; i < b.length; i++) {						arr[k++] = b[i];					}				}			}			digit++;			radixSortLSD(arr, digit);		}	}	private static int[] appendItem(int[] bucketArr, int val) {		if (bucketArr == null || bucketArr.length == 0) {			return new int[]{val};		}		// 拷贝一下原来桶的序列，并增加一位		int[] arr = Arrays.copyOf(bucketArr, bucketArr.length + 1);		arr[bucketArr.length] = val;		return arr;	}}