定义：基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。 思路：
①.找出序列中最大数的位数；
②.根据序列中元素个位数的数值，依次将元素放到0-9的桶子中； 再将桶子中的元素重新取出并串联起来。
③.根据序列中元素的十位数的数值，依次将元素放到0-9的桶子中；再将桶子中的元素重新取出并串联起来。
④.重复以上步骤，直到最高位，此时，排序完毕。
(注：桶的数据结构为队列，即元素的存取为先进先出) 图解： 总结：基数排序是一种非比较型正整数排序算法，它是桶排序的其中一种扩展，其优点是效率高，但是占用内存大。
代码实现：
/** * 基数排序 * @param arr */ public static void baseSort(int[] arr) { //首先确定序列中最大的数的位数，即需要排序的次数 int max = arr[0]; //记录最大数 for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } int time = 0; //排序次数 //判断位数; while (max > 0) { max /= 10; time++; } //建立10个队列 List<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); for (int i = 0; i < 10; i++) { ArrayList<Integer> queue = new ArrayList<Integer>(); list.add(queue); } //进行time次分配和收集 for (int i = 0; i < time; i++) { //分配数组元素 for (int j = 0; j < arr.length; j++) { //得到元素在i位置上的数(0：个位，1：十位，2：百位) int x = arr[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i); // 获取x对应队列，并将数据保存到该队列中 ArrayList<Integer> queue = list.get(x); queue.add(arr[j]); } int count = 0;//元素计数器 // 串联队列中的元素 for (int k = 0; k < 10; k++) { // 如果队列中有元素，将队列中的元素以先进先出形式取出 while (list.get(k).size() > 0) { // 取出队列中的元素 List<Integer> queue = list.get(k); arr[count] = queue.get(0); //将取出的元素从队列中移除 queue.remove(0); // 计数器加1 count++; } } } }