基本介绍
基数排序（Radix Sort）是一种非比较型的排序算法，它通过将待排序元素按照高位和低位的顺序依次进行排序，从而实现整体的排序效果。其基本步骤如下：
- 首先，将待排序的元素按照最低有效位（LSB）的值进行排序。可以使用计数排序或桶排序等稳定的排序算法来完成这一步。
- 接着，将上一步排序后的结果按照次低有效位进行排序。同样地，可以使用稳定的排序算法对每个桶中的元素进行排序。
- 重复上述步骤，直到按照最高有效位进行排序。最终得到的排序结果就是有序的。
在基数排序过程中，每一轮排序都会根据当前有效位的值，将所有元素分配到不同的桶中。桶的数量通常为10，对应于十进制数系统中的10个数字（0-9）。每个桶中的元素按照顺序排列，然后按照桶的顺序依次取出，形成新的待排序序列。通过多次的桶排序，最终可以得到整体有序的结果。
时间空间复杂度分析
时间复杂度：基数排序的时间复杂度为O(d*(n b))，其中n是待排序元素的个数，d是元素的最大位数，b是桶的数量。在每一轮排序中，需要对n个元素进行分配到b个桶的操作，然后将桶中的元素按照顺序取出，这两个操作的时间复杂度均为O(n)。对于最大位数为d的情况，需要进行d轮排序操作。因此，总的时间复杂度为O(d*(n b))。
空间复杂度：基数排序的空间复杂度主要取决于桶的数量b。在每一轮排序中，需要使用额外的存储空间来存放各个桶。如果使用稳定的排序算法对每个桶中的元素进行排序，那么需要额外的O(n)空间。因此，基数排序的空间复杂度为O(n b)。
基数排序的时间复杂度和空间复杂度都与元素的位数和桶的数量有关。当元素的位数较小且分布均匀时，基数排序的效率较高。但是，当元素的位数非常大或者元素的分布不均匀时，基数排序的时间复杂度和空间复杂度可能会增加。此外，基数排序对于负数的排序需要进行额外的处理。
伪代码
代码语言：javascript复制// 获取数组中的最大值
function getMax(arr):
max = arr[0]
for i = 1 to length(arr) do:
if arr[i] > max then:
max = arr[i]
return max
// 对数组按照指定位数进行计数排序
function countingSort(arr, exp):
n = length(arr)
output = new array with size n
count = new array with size 10 initialized to 0
// 统计每个数字出现的次数
for i = 0 to n-1 do:
index = (arr[i] / exp) % 10
count[index] = count[index] 1
// 计算每个数字在输出数组中的位置
for i = 1 to 9 do:
count[i] = count[i] count[i-1]
// 将元素按照位数排序到输出数组中
for i = n-1 to 0 do:
index = (arr[i] / exp) % 10
output[count[index]-1] = arr[i]
count[index] = count[index] - 1
// 将排序结果复制回原数组
for i = 0 to n-1 do:
arr[i] = output[i]
// 基数排序算法
function radixSort(arr):
max = getMax(arr)
// 从最低有效位开始，依次对每个位进行计数排序
exp = 1
while max / exp > 0 do:
countingSort(arr, exp)
exp = exp * 10
通过getMax函数获取数组中的最大值，以确定需要进行多少轮排序。然后，使用countingSort函数对数组按照每个位数进行计数排序。最后，在radixSort函数中，从最低有效位开始，依次对每个位进行计数排序，直到最高有效位。最终得到有序的数组。
基于java的实现
代码语言：javascript复制import java.util.Arrays;
public class RadixSort {
// 获取数组中的最大值
public static int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i ) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// 对数组按照指定位数进行计数排序
public static void countingSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
// 统计每个数字出现的次数
for (int i = 0; i < n; i ) {
int index = (arr[i] / exp) % 10;
count[index] ;
}
// 计算每个数字在输出数组中的位置
for (int i = 1; i < 10; i ) {
count[i] = count[i - 1];
}
// 将元素按照位数排序到输出数组中
for (int i = n - 1; i >= 0; i--) {
int index = (arr[i] / exp) % 10;
output[count[index] - 1] = arr[i];
count[index]--;
}
// 将排序结果复制回原数组
System.arraycopy(output, 0, arr, 0, n);
}
// 基数排序算法
public static void radixSort(int[] arr) {
int max = getMax(arr);
// 从最低有效位开始，依次对每个位进行计数排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
// 测试示例
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
System.out.println("Sorted array: " Arrays.toString(arr));
}
}
countingSort函数实现了计数排序算法。它接受两个参数：待排序的数组arr和当前位数exp。首先，创建一个辅助数组output和一个计数数组count，并将count初始化为大小为10的数组，初始值都为0。然后，遍历数组arr，统计每个数字出现的次数，将统计结果存入count数组中。接下来，计算每个数字在输出数组output中的位置，通过累加前面的计数值，将其存入count数组中。最后，再次遍历数组arr，将元素按照位数排序到输出数组output中，并更新计数数组count。最后，将排序结果复制回原数组arr。
radixSort函数是基数排序的主要实现。它接受一个数组arr作为输入。首先，使用getMax函数获取数组中的最大值，以确定需要进行多少轮排序。然后，从最低有效位开始，依次对每个位进行计数排序，通过调用countingSort函数实现。每次排序完毕，位数exp乘以10，以便下一轮排序使用。
