admin管理员组文章数量:1441537
常用的排序算法之基数排序（Radix Sort）
基数排序（Radix Sort）起源或原理
基数排序（Radix Sort）是非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。它按照从低位到高位（或者从高位到低位）依次对待排序的元素进行排序，直到所有的位数都被排序完毕。基数排序的思想借鉴了人类的计数排序法，即按照十进制数的每一位数来分别进行排序。
定义
基数排序（Radix Sort）是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
引伸义
基数排序可以看作是一种“分配-收集”的排序过程，它按照数字的每一位进行排序，并通过多次分配和收集来完成整个排序过程。基数排序的思想可以扩展到其他非整数的排序场景，比如字符串的字典序排序等。
优缺点
优点：
- 适用于非负整数，且时间复杂度为O(d(n+k))，其中d为数字的位数，n为待排序元素个数，k为数字取值范围。
- 基数排序是稳定的排序算法。
缺点：
- 不适用于负数排序。
- 当待排序元素不是整数时，需要将其转换为整数或字符串才能使用基数排序。
- 对于数据分布不均匀的情况，基数排序可能不是最优选择。
使用场景
基数排序适用于待排序数据为整数，且整数的位数相差不大的情况。在实际应用中，基数排序经常用于对字符串的字典序排序，比如文件名排序、学号排序等。
使用数据一步步举例
假设有一组待排序的非负整数：[170, 45, 75, 90, 802, 24, 2, 66]。
- 按个位排序：
- 分配：
[2, 24, 45, 66, 75, 90, 170, 802] - 收集：[2, 24, 45, 66, 75, 90, 170, 802]（已经是按个位排序）
- 分配：
- 按十位排序：
- 分配（使用稳定排序）：
- 0位桶：[2, 24, 90, 802]
- 5位桶：[45]
- 6位桶：[66]
- 7位桶：[75]
- 1位桶：[170]
- 收集：[2, 24, 45, 66, 75, 90, 170, 802]（已经是按十位排序）
- 分配（使用稳定排序）：
- 按百位排序（由于这组数中只有802有百位，所以这一步实际上只影响802的位置）：
- 分配（使用稳定排序）：
- 0位桶：[2, 24, 45, 66, 75, 90, 170]
- 8位桶：[802]
- 收集：[2, 24, 45, 66, 75, 90, 170, 802]（已经是按百位排序，即完全排序）
- 分配（使用稳定排序）：
Java示例代码
代码语言：javascript代码运行次数：0运行复制public class RadixSort {
// 基数排序的主方法
public static void radixSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
// 获取数组中最大数的位数
int maxDigit = getMaxDigit(arr);
// 从最低位开始排序
for (int digit = 1; digit <= maxDigit; digit++) {
// 调用计数排序对指定位进行排序
countingSort(arr, digit);
}
}
// 获取数组中最大数的位数
private static int getMaxDigit(int[] arr) {
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
int digit = 0;
while (max > 0) {
max /= 10;
digit++;
}
return digit;
}
// 计数排序方法，用于基数排序中的每一位
private static void countingSort(int[] arr, int digit) {
int maxVal = getMaxValue(arr, digit); // 获取当前位的最大值
int[] output = new int[arr.length]; // 临时数组，用于存储排序后的结果
int[] count = new int[maxVal + 1]; // 计数数组
// 初始化计数数组
for (int i = 0; i <= maxVal; i++) {
count[i] = 0;
}
// 计算每个元素在当前位上的出现次数
for (int i = 0; i < arr.length; i++) {
int index = getDigit(arr[i], digit);
count[index]++;
}
// 修改计数数组，变为前缀和
for (int i = 1; i <= maxVal; i++) {
count[i] += count[i - 1];
}
// 从后向前遍历，将元素放到正确的位置上
for (int i = arr.length - 1; i >= 0; i--) {
int index = getDigit(arr[i], digit);
output[count[index] - 1] = arr[i];
count[index]--;
}
// 将排序后的元素复制回原数组
System.arraycopy(output, 0, arr, 0, arr.length);
}
// 获取指定位置上的数字（0-based index）
private static int getDigit(int num, int digit) {
return (num / (int)Math.pow(10, digit - 1)) % 10;
}
// 获取数组中在当前位上的最大值
private static int getMaxValue(int[] arr, int digit) {
int maxVal = 0;
for (int num : arr) {
int digitVal = getDigit(num, digit);
if (digitVal > maxVal) {
maxVal = digitVal;
}
}
return maxVal;
}
// 测试方法
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
} 这个完整的代码示例包括基数排序的主方法radixSort，辅助方法getMaxDigit来获取最大数的位数，countingSort来实现计数排序以在每个位上进行排序，getDigit来获取指定位置上的数字，以及getMaxValue来获取数组中在当前位上的最大值。最后，main方法用于测试基数排序算法。
本文标签： 常用的排序算法之基数排序（Radix Sort）
版权声明：本文标题：常用的排序算法之基数排序（Radix Sort） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/biancheng/1747940917a2780382.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论