详细描述
从基数排序的描述可以看得出,其适用于整数,但是,整数也可以表达字符串(比如名字或时间)和特定格式的浮点数,因此基数排序并不只是适用于整数。
基数排序详细的执行步骤如下:
- 首先准备 10 个桶,分别用于存储所在位数为 0 ~ 9 的数;
- 提取出序列中元素的个位,将该元素移动到对应个位所属的桶内;
- 重复执行第 2 步,从个位、十位、百位直到最大元素的最大位数,没有所在位时赋为 0;
- 执行完第 3 步,组合每个桶内的元素成有序序列。
算法图解
问题解疑
基数排序的复杂度是多少?
基数排序的时间复杂度和待排序序列的最大位数有关系,由于需要对每一个位数遍历一次序列,基数排序的时间复杂度是
基数排序的空间复杂度是
基数排序和快速排序哪个效率更好?
基数排序是一种空间换时间的非比较类排序算法,其时间复杂度是
从时间复杂度上看,主要在于其系数的比较。通常是,待排序序列的最大位数越大, 基数排序的效率就越低,这时选择快速排序则更优;如果数据量非常大的时候,则基数排序比较占优。
代码实现
排序抽象类
package cn.fatedeity.algorithm.sort; /** * 排序抽象类 */ public abstract class Sort { protected void swap(int[] numbers, int src, int target) { int temp = numbers[src]; numbers[src] = numbers[target]; numbers[target] = temp; } public abstract int[] sort(int[] numbers); }
计数排序类
package cn.fatedeity.algorithm.sort; import java.util.List; import java.util.ArrayList; /** * 计数排序算法类 */ public class RadixSort extends Sort { public int[] sort(int[] numbers) { if (numbers.length == 0) { return numbers; } int min = numbers[0], max = numbers[0]; for (int number : numbers) { if (number < min) { min = number; } if (number > max) { max = number; } } int k = String.valueOf(Math.max(Math.abs(min), Math.abs(max))).length(); List<List<Integer>> buckets = new ArrayList<>(); for (int i = 0; i < 19; i++) { buckets.add(new ArrayList<>()); } int x = 1; while (x <= k) { for (int number : numbers) { int index = (number / (int) Math.pow(10, x - 1)) % 10; List<Integer> bucket = buckets.get(index + 9); bucket.add(number); } int index = 0; for (int i = 0; i < buckets.size(); i++) { for (int number : buckets.get(i)) { numbers[index++] = number; } buckets.set(i, new ArrayList<>()); } x++; } return numbers; } }
折叠