1
基数排序的简单理解 - 程序员翔仔
source link: https://www.cnblogs.com/fatedeity/p/16437619.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
从基数排序的描述可以看得出，其适用于整数，但是，整数也可以表达字符串（比如名字或时间）和特定格式的浮点数，因此基数排序并不只是适用于整数。
基数排序详细的执行步骤如下：
- 首先准备 10 个桶，分别用于存储所在位数为 0 ~ 9 的数；
- 提取出序列中元素的个位，将该元素移动到对应个位所属的桶内；
- 重复执行第 2 步，从个位、十位、百位直到最大元素的最大位数，没有所在位时赋为 0；
- 执行完第 3 步，组合每个桶内的元素成有序序列。
基数排序的复杂度是多少？
基数排序的时间复杂度和待排序序列的最大位数有关系，由于需要对每一个位数遍历一次序列，基数排序的时间复杂度是 O(n×k)，其中 k 是最大位数。
基数排序的空间复杂度是 O(n+k)，其中 k 是桶的数量。
基数排序和快速排序哪个效率更好？
基数排序是一种空间换时间的非比较类排序算法，其时间复杂度是 O(n×k)；快速排序是一种常规的比较类排序算法，其时间复杂度是 O(nlog2n)。
从时间复杂度上看，主要在于其系数的比较。通常是，待排序序列的最大位数越大， 基数排序的效率就越低，这时选择快速排序则更优；如果数据量非常大的时候，则基数排序比较占优。
排序抽象类
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; }}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK