基数排序（JAVA实现）

基本介绍：
（1）通过键值得各个位的值，将要排序的元素分配至一些桶中，达到排序的作用
（2）基数排序法是属于稳定性的排序，基数排序法是效率高的稳定排序法
（3）基数排序是桶排序的扩展

稳定性：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]前面，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的，否则称为不稳定的。

图解：

代码实现：

public class RadixSort {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		//定义测试数组
		int[] arr= {53,3,542,748,14,214};
		radixSort(arr);
	}
	
	public static void radixSort(int[] arr) {
		//得到数组中的最大数的小标，这样才能知道要循环多少轮
		int max=0;
		for(int maxindex=1;maxindex<arr.length;maxindex++) {
			if(arr[max]<arr[maxindex]) {
				max=maxindex;
			}
		}
		//得到数字共有几位数
		int times=(arr[max]+"").length();
		for(int time=0,n=1;time<times;time++,n*=10) {
			//创建桶,共有10个桶，每个桶最多有arr.length个数据
			int[][] bucket=new int[10][arr.length];
			//用于记录每个桶中有多少数据，用于遍历桶中的数据
			int[] bucketElementsCount=new int[10];
			//开始遍历数组
			for(int i=0;i<arr.length;i++) {
				int digitOfElement=(int) ((arr[i]/n)%10); //取出对应的位数
				//将其存入bucket中
				bucket[digitOfElement][bucketElementsCount[digitOfElement]]=arr[i];
				bucketElementsCount[digitOfElement]++;
			}
			
			//将bucket中的数据输出到arr中
			int index=0;
			for(int i=0;i<bucketElementsCount.length;i++) {
				if(bucketElementsCount[i]!=0) {
					for(int j=0;j<bucketElementsCount[i];j++) {
						arr[index]=bucket[i][j];
						index++;
					}
				}
			}
			System.out.println("第"+(time+1)+"轮过后的数组为："+Arrays.toString(arr));
		}
	}

}

测试结果：
第1轮过后的数组为：[542, 53, 3, 14, 214, 748]
第2轮过后的数组为：[3, 14, 214, 542, 748, 53]
第3轮过后的数组为：[3, 14, 53, 214, 542, 748]