基数排序的原理是什么？
- 内容介绍
- 相关推荐
本文共计1058个文字，预计阅读时间需要5分钟。
基数排序是一种非比较排序算法，适用于整数排序。其原理是将整数分割成不同的数位，然后根据数位的大小进行排序。具体步骤如下：
1. 将待排序的整数按照最低位（个位）开始，依次向高位分割成不同的数位。
2.对每个数位，使用计数排序或其他排序算法对分割出的数进行排序。
3.将排序后的数重新组合成整数，得到最终的排序结果。
例如，对整数集合 {170, 45, 75, 90, 802, 24, 2, 66} 进行基数排序：
1. 个位排序：{170, 24, 45, 75, 90, 2, 66, 802}
2.十位排序：{2, 24, 45, 66, 75, 90, 170, 802}
3.百位排序：{2, 24, 45, 66, 75, 90, 170, 802}
最终排序结果为：{2, 24, 45, 66, 75, 90, 170, 802}
基数排序是桶排序的一种扩展使用，同样是一种非比较的整数排序算法，其原理是将整数位数切割成不同的数字，然后按每个位数分别比较。 详细描述从基数排序的描述可以看得出，其适用于整数，但是，整数也可以表达字符串（比如名字或时间）和特定格式的浮点数，因此基数排序并不只是适用于整数。
基数排序详细的执行步骤如下：
- 首先准备 10 个桶，分别用于存储所在位数为 0 ~ 9 的数；
- 提取出序列中元素的个位，将该元素移动到对应个位所属的桶内；
- 重复执行第 2 步，从个位、十位、百位直到最大元素的最大位数，没有所在位时赋为 0；
- 执行完第 3 步，组合每个桶内的元素成有序序列。
基数排序的时间复杂度和待排序序列的最大位数有关系，由于需要对每一个位数遍历一次序列，基数排序的时间复杂度是 \(O(n \times k)\)，其中 k 是最大位数。
基数排序的空间复杂度是 \(O(n+k)\)，其中 k 是桶的数量。
基数排序和快速排序哪个效率更好？基数排序是一种空间换时间的非比较类排序算法，其时间复杂度是 \(O(n \times k)\)；快速排序是一种常规的比较类排序算法，其时间复杂度是 \(O(n\log_2n)\)。
从时间复杂度上看，主要在于其系数的比较。通常是，待排序序列的最大位数越大， 基数排序的效率就越低，这时选择快速排序则更优；如果数据量非常大的时候，则基数排序比较占优。
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;
}
}
首发于翔仔的个人博客，点击查看更多。
本文共计1058个文字，预计阅读时间需要5分钟。
基数排序是一种非比较排序算法，适用于整数排序。其原理是将整数分割成不同的数位，然后根据数位的大小进行排序。具体步骤如下：
1. 将待排序的整数按照最低位（个位）开始，依次向高位分割成不同的数位。
2.对每个数位，使用计数排序或其他排序算法对分割出的数进行排序。
3.将排序后的数重新组合成整数，得到最终的排序结果。
例如，对整数集合 {170, 45, 75, 90, 802, 24, 2, 66} 进行基数排序：
1. 个位排序：{170, 24, 45, 75, 90, 2, 66, 802}
2.十位排序：{2, 24, 45, 66, 75, 90, 170, 802}
3.百位排序：{2, 24, 45, 66, 75, 90, 170, 802}
最终排序结果为：{2, 24, 45, 66, 75, 90, 170, 802}
基数排序是桶排序的一种扩展使用，同样是一种非比较的整数排序算法，其原理是将整数位数切割成不同的数字，然后按每个位数分别比较。 详细描述从基数排序的描述可以看得出，其适用于整数，但是，整数也可以表达字符串（比如名字或时间）和特定格式的浮点数，因此基数排序并不只是适用于整数。
基数排序详细的执行步骤如下：
- 首先准备 10 个桶，分别用于存储所在位数为 0 ~ 9 的数；
- 提取出序列中元素的个位，将该元素移动到对应个位所属的桶内；
- 重复执行第 2 步，从个位、十位、百位直到最大元素的最大位数，没有所在位时赋为 0；
- 执行完第 3 步，组合每个桶内的元素成有序序列。
基数排序的时间复杂度和待排序序列的最大位数有关系，由于需要对每一个位数遍历一次序列，基数排序的时间复杂度是 \(O(n \times k)\)，其中 k 是最大位数。
基数排序的空间复杂度是 \(O(n+k)\)，其中 k 是桶的数量。
基数排序和快速排序哪个效率更好？基数排序是一种空间换时间的非比较类排序算法，其时间复杂度是 \(O(n \times k)\)；快速排序是一种常规的比较类排序算法，其时间复杂度是 \(O(n\log_2n)\)。
从时间复杂度上看，主要在于其系数的比较。通常是，待排序序列的最大位数越大， 基数排序的效率就越低，这时选择快速排序则更优；如果数据量非常大的时候，则基数排序比较占优。
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;
}
}
首发于翔仔的个人博客，点击查看更多。