基数排序（Radix Sort）详解
一、什么是基数排序？
基数排序（Radix Sort）是一种非比较型整数排序算法，它通过逐位处理数字来实现排序。与快速排序、归并排序等基于比较的排序算法差别，基数排序使用了每个数字的位值举行排序，因此可以在O(n)的时间复杂度内完成排序使命。基数排序适用于对正整数、负整数以及固定长度的字符串举行排序。
1. 什么是基数
基数是指数字体系中的基本单元或底子值。它决定了一个数位上大概有多少种差别的符号或数值。例如，在十进制体系中，基数是10，由于每一位上有10种大概的符号（0到9）。类似地，在二进制体系中，基数是2，由于每一位上只有两种大概的符号（0和1）。
- 对于十进制整数：基数为10，表示每一位上有0到9这10个大概的值。
- 对于二进制整数：基数为2，表示每一位上有0和1这两个大概的值。
- 对于十六进制整数：基数为16，表示每一位上有0到F（即0到15）这16个大概的值。
- 对于字符串：假如不思量大小写，基数为26，表示每一位上有a到z这26个大概的字母。
基数排序通过逐位处理这些数字来实现排序。每次处理一位时，都使用一种线性时间复杂度的排序算法（如计数排序）对当前位上的所有数字举行排序。
2. 基数排序的特点
- 稳固性：基数排序是稳固的排序算法，即相称元素的相对序次在排序后不会改变。
- 时间复杂度：
- 对于d位数且每一位有k个大概值的情况，时间复杂度为O(d * (n + k))。
- 空间复杂度：由于需要额外的空间来存储中央结果，空间复杂度为O(n + k)。
3. 基数的选择对性能的影响
选择合适的基数对基数排序的性能有很大影响：
- 基数越大：每次处理的位数越多，需要更多的空间来存储计数信息，但总的排序次数减少。
- 基数越小：每次处理的位数较少，所需的额外空间较少，但总的排序次数增长。
因此，选择合适的基数可以在时间和空间之间找到一个均衡点。对于大多数应用场景，基数通常选择为10（十进制），但在某些特定情况下（如处理二进制数据或十六进制数据），可以选择其他基数。
二、基数排序的工作原理
基数排序有两种主要的实现方式：
- 最低有效位优先（LSD, Least Significant Digit first）：从最低位开始逐位排序。
- 最高有效位优先（MSD, Most Significant Digit first）：从最高位开始逐位排序。
本文主要介绍最低有效位优先（LSD）的实现方式。
基本步调
- 确定最大数的位数：找到待排序数组中的最大数，并确定其位数。
- 按位排序：从最低位到最高位依次对每一位举行排序。每次排序可以使用计数排序（Counting Sort）或其他线性时间排序算法。
- 重复步调2：直到所有位都处理完毕。
三、Java实现基数排序
以下是基于最低有效位（LSD）的基数排序算法的Java实现示例：
示例代码一
基数为10，可以使用LinkedList<Integer>[] bucket = new LinkedList[10];来缓存排序的临时结果。
- public static void radixSort2(int[] arr) {
- // 查找数组中最大的数字
- int max = arr[0];
- for (int i = 1; i < arr.length; i++) {
- if(arr[i] > max) {
- max = arr[i];
- }
- }
- // 基数
- LinkedList<Integer>[] bucket = new LinkedList[10];
- for (int i = 0; i < bucket.length; i++) {
- bucket[i] = new LinkedList<>();
- }
- // 从低位到高位逐位处理
- for (int exp = 1; max / exp > 0; exp *= 10) {
- // 逐个将元素放入基数桶中
- for (int i : arr) {
- bucket[i / exp % 10].add(i);
- }
- int index = 0;
- // 收集排序结果
- for (int i = 0; i < bucket.length; i++) {
- while(!bucket[i].isEmpty()) {
- arr[index++] = bucket[i].remove();
- }
- }
- }
- }
由于上述代码中的LinkedList服从不是很高，可以使用数组更换LinkedList进而优化性能。
- public static void radixSort2(int[] arr) {
- // 查找数组中最大的数字
- int max = arr[0];
- for (int i = 1; i < arr.length; i++) {
- if(arr[i] > max) {
- max = arr[i];
- }
- }
- // 从低位到高位逐位处理
- for (int exp = 1; max / exp > 0; exp *= 10) {
- // System.out.println("exp=" + exp);
- // 基数数组，相当于桶
- int[] bucket = new int[10];
- // 逐个将数组元素放入桶中
- for (int i : arr) {
- bucket[i / exp % 10]++;
- }
- // System.out.println("bucket1: " + Arrays.toString(bucket));
- // 计算排序后的位置
- for (int i = 1; i < bucket.length; i++) {
- bucket[i] += bucket[i - 1];
- }
- // System.out.println("bucket2: " + Arrays.toString(bucket));
- // 临时数组，存储此轮排序后的结果
- int[] temp = new int[arr.length];
- for (int i = arr.length - 1; i >= 0; i--) {
- int j = arr[i] / exp % 10;
- temp[bucket[j] - 1] = arr[i];
- bucket[j] --;
- }
- // System.out.println("temp: " + Arrays.toString(temp));
-
- // 收集排序结果
- System.arraycopy(temp, 0, arr, 0, temp.length);
- }
- }
1. 初始化
这里以数组[194, 451, 934, 847, 223, 373, 223, 6, 965, 510]为例，演示基数排序。
数组中有两个元素是223，为了演示该排序的稳固性，给后面的223添加浅蓝色背景。
2. 遍历数组元素，按个位值将它们放入基数桶中
2.1 按个位值大小分别放入差别的桶中
2.2 处理194：个位值为4，放入索引为4的桶中。
2.3 处理451：个位值为1，放入索引为1的桶中。
2.4 依次处理数组中的别的元素，得到如下结果。
3. 网络该轮排序结果
3.1 遍历所有的基数桶，并取出所有的元素，按序次放回数组中
3.2 读取索引为0的桶中数据，将510放回数组索引为0的位置。
3.3 读取索引为1的桶中数据，将451放回数组索引为1的位置。
3.4 继续读取索引为2-9的桶中数据，分别将223、373、223、194、934、965、6、847放回数组索引2-9的位置，结果如上图。
4. 遍历数组元素，按十位值将它们放入基数桶中
4.1 按十位值大小分别放入差别的桶中
4.2 依次处理数组中的元素，得到如下结果。
5. 网络该轮排序结果
6. 遍历数组元素，按百位值将它们放入基数桶中
7. 网络该轮排序结果
排序竣事，结果是：[6, 194, 223, 223, 373, 451, 510, 847, 934, 965]。
五、时间复杂度和空间复杂度
- 时间复杂度：
对于d位数且每一位有k个大概值的情况，时间复杂度为O(d * (n + k))。此中，n是数组长度，d是最大数的位数，k是基数（如十进制下的基数为10）。
- 空间复杂度：
由于需要额外的空间来存储中央结果，空间复杂度为O(n + k)。
六、总结
基数排序是一种非常有效的排序算法，特别适用于对大量整数举行排序。与快速排序和归并排序差别，基数排序不是基于比较的，因此它可以在线性时间内完成排序使命。然而，基数排序也有其范围性，好比只适用于整数和固定长度的字符串等数据类型。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
