基数排序
常见的数据元素一般是由若干位组成的，比如字符串由若干字符组成，整数由若干位 0~9 数字组成。
基数排序按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，同时每一轮排序都基于上轮排序后的结果；当我们将所有的位排序后，整个数组就达到有序状态。基数排序不是基于比较的算法。
基数是什么意思？对于十进制整数，每一位都只可能是 0~9 中的某一个，总共 10 种可能。那 10 就是它的基，同理二进制数字的基为 2；对于字符串，如果它使用的是 8 位的扩展 ASCII 字符集，那么它的基就是 256。
基数排序有两种方法：
MSD 从高位开始进行排序
LSD 从低位开始进行排序
对于大小范围为 0~9 的数的组合（若是两位数，就是个位数和十位数的组合），于是可以准备十个桶，然后放到对应的桶里，然后再把桶里的数按照 0 号桶到 9 号桶的顺序取出来即可。
代码实现
public class RadixSort { public static final int[] ARRAY = {82, 50, 21, 5, 66, 48, 43, 79, 14, 37, 25}; public static int[] sort(int[] array) { if (array.length < 2) return array; //根据最大值算出位数 int max = array[0]; for (int temp : array) { if (temp > max) { max = temp; } } //算出位数digit int maxDigit = 0; while (max != 0) { max /= 10; maxDigit++; } //创建桶并初始化 ArrayList<ArrayList<Integer>> bucket = new ArrayList<>(); for (int i = 0; i < 10; i++) { bucket.add(new ArrayList<>()); } //按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，每一轮排序都基于上轮排序后的结果 int mold = 10;//取模运算 int div = 1;//获取对应位数的值 for (int i = 0; i < maxDigit; i++, mold *= 10, div *= 10) { for (int j = 0; j < array.length; j++) { //获取个位/十位/百位...... int num = (array[j] % mold) / div; //把数据放入到对应的桶里 bucket.get(num).add(array[j]); } //把桶中的数据重新写回去，并把桶的元素清空，开始第二轮排序 int index = 0; for (int k = 0; k < bucket.size(); k++) { //桶中对应的数据 ArrayList<Integer> list = bucket.get(k); for (int m = 0; m < list.size(); m++) { array[index++] = list.get(m); } //清除桶 bucket.get(k).clear(); } } return array; } public static void print(int[] array) { for (int i : array) { System.out.print(i + " "); } System.out.println(""); } public static void main(String[] args) { print(ARRAY); System.out.println("============================================"); print(sort(ARRAY)); }}
复制代码
时间复杂度
计数排序算法的时间复杂度是 O(N+M)，基数排序算法执行了 k 次计数排序，所以基数排序算法的时间复杂度为 O(K(N+M))。
算法稳定性
从上面的分析可以看出，相同元素会按照顺序放进固定的桶内，取出的时候也是按照顺序取出来的，所以基数排序算法是一种稳定的排序算法。
基数排序 vs 桶排序 vs 计数排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异
基数排序：根据每一位的关键字来分配桶
桶排序：存储一定范围的值
计数排序：每个桶只存储一个类型值，但是数量不限
评论