## **基数排序** 基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。 排序过程：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。 ## **算法描述** 1. 取得数组中的最大数，并取得位数； 2. arr为原始数组，从最低位开始取每个位组成radix数组； 3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）； ## **稳定性** 通过上面的排序过程，我们可以看到，每一轮映射和收集操作，都保持从左到右的顺序进行，如果出现相同的元素，则保持他们在原始数组中的顺序。可见，基数排序是一种稳定的排序。 ## **适用场景** 基数排序要求较高，元素必须是整数，整数时长度10W以上，最大值100W以下效率较好，但是基数排序比其他排序好在可以适用字符串，或者其他需要根据多个条件进行排序的场景，例如日期，先排序日，再排序月，最后排序年 ，其它排序算法可是做不了的。 ## **JAVA代码实现** ``` public abstract class Sorter { public abstract void sort(int[] array); } public class RadixSorter extends Sorter { private int radix; public RadixSorter() { radix = 10; } @Override public void sort(int[] array) { // 数组的第一维表示可能的余数0-radix，第二维表示array中的等于该余数的元素 // 如：十进制123的个位为3，则bucket[3][] = {123} int[][] bucket = new int[radix][array.length]; int distance = getDistance(array); // 表示最大的数有多少位 int temp = 1; int round = 1; // 控制键值排序依据在哪一位 while (round <= distance) { // 用来计数：数组counter[i]用来表示该位是i的数的个数 int[] counter = new int[radix]; // 将array中元素分布填充到bucket中，并进行计数 for (int i = 0; i < array.length; i++) { int which = (array[i] / temp) % radix; bucket[which][counter[which]] = array[i]; counter[which]++; } int index = 0; // 根据bucket中收集到的array中的元素，根据统计计数，在array中重新排列 for (int i = 0; i < radix; i++) { if (counter[i] != 0) for (int j = 0; j < counter[i]; j++) { array[index] = bucket[i][j]; index++; } counter[i] = 0; } temp *= radix; round++; } } private int getDistance(int[] array) { int max = computeMax(array); int digits = 0; int temp = max / radix; while(temp != 0) { digits++; temp = temp / radix; } return digits + 1; } private int computeMax(int[] array) { int max = array[0]; for(int i=1; i<array.length; i++) { if(array[i]>max) { max = array[i]; } } return max; } } ```