【算法系列】基数排序

文章目录

基数排序（Radix Sort）详解
- 一、什么是基数排序？
- - 1. 什么是基数
  - 2. 基数排序的特点
  - 3. 基数的选择对性能的影响
- 二、基数排序的工作原理
- - 基本步骤
- 三、Java实现基数排序
- - 示例代码一
  - 示例代码二
- 四、排序演示
- - 1. 初始化
  - 2. 遍历数组元素，按个位值将它们放入基数桶中
  - 3. 收集该轮排序结果
  - 4. 遍历数组元素，按十位值将它们放入基数桶中
  - 5. 收集该轮排序结果
  - 6. 遍历数组元素，按百位值将它们放入基数桶中
  - 7. 收集该轮排序结果
- 五、时间复杂度和空间复杂度
- 六、总结

基数排序（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];来缓存排序的临时结果。

java">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进而优化性能。

java">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的位置，结果如上图。