基数排序原理及实战
- 2020 年 1 月 16 日
- 筆記
基数排序
原理
我们来看这样一个排序问题。假设我们有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，你有什么比较快速的排序方法呢？
我们之前讲的快排，时间复杂度可以做到 O(nlogn)，还有更高效的排序算法吗？桶排序、计数排序能派上用场吗？手机号码有 11 位，范围太大，显然不适合用这两种排序算法。针对这个排序问题，有没有时间复杂度是 O(n) 的算法呢？现在我就来介绍一种新的排序算法，基数排序。
刚刚这个问题里有这样的规律：假设要比较两个手机号码 a，b 的大小，如果在前面几位中，a 手机号码已经比 b 手机号码大了，那后面的几位就不用看了。
借助稳定排序算法，这里有一个巧妙的实现思路。还记得我们第 11 节中，在阐述排序算法的稳定性的时候举的订单的例子吗？我们这里也可以借助相同的处理思路，先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后，手机号码就都有序了。
手机号码稍微有点长，画图比较不容易看清楚，我用字符串排序的例子，画了一张基数排序的过程分解图，你可以看下。
注意，这里按照每位来排序的排序算法要是稳定的，否则这个实现思路就是不正确的。因为如果是非稳定排序算法，那最后一次排序只会考虑最高位的大小顺序，完全不管其他位的大小关系，那么低位的排序就完全没有意义了。
根据每一位来排序，我们可以用刚讲过的桶排序或者计数排序，它们的时间复杂度可以做到 O(n)。如果要排序的数据有 k 位，那我们就需要 k 次桶排序或者计数排序，总的时间复杂度是 O(k*n)。当 k 不大的时候，比如手机号码排序的例子，k 最大就是 11，所以基数排序的时间复杂度就近似于 O(n)。
实际上，有时候要排序的数据并不都是等长的，比如我们排序牛津字典中的 20 万个英文单词，最短的只有 1 个字母，最长的我特意去查了下，有 45 个字母，中文翻译是尘肺病。对于这种不等长的数据，基数排序还适用吗？
实际上，我们可以把所有的单词补齐到相同长度，位数不够的可以在后面补“0”，因为根据ASCII 值，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺序。这样就可以继续用基数排序了。
我来总结一下，基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。
示例
import java.util.ArrayList; import java.util.List; /** * 基数排序 * （1）从低位开始，每一位用桶排序 * @author huangy on 2020-01-06 */ public class BaseSort { public static void baseSort(int[] arr) { // 计算出数字的最大位数 int digit = getMaxDigit(arr); // 遍历每一位，依次进行桶排序 int digitValue; for (int k = 1; k <= digit; k++) { List<Node> nodeList = new ArrayList<>(arr.length); int maxDigitValue = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { // 取出该数字，当前位的值，不够位则返回0 digitValue = getDigitValue(arr[i], k); Node node = new Node(); node.digitValue = digitValue; node.realValue = arr[i]; nodeList.add(node); if (digitValue > maxDigitValue) { maxDigitValue = digitValue; } } // 桶排序 int[] countArr = new int[maxDigitValue + 1]; for (Node node : nodeList) { countArr[node.digitValue]++; } int[] addressArr = new int[countArr.length]; addressArr[0] = countArr[0]; for (int j = 0; j < (addressArr.length - 1); j++) { addressArr[j + 1] = addressArr[j] + countArr[j + 1]; } // 先存放到临时数组 List<Node> temNodeList = new ArrayList<>(nodeList); int i = nodeList.size() - 1; /* * 这里一定要注意，从后往前遍历，那么才是稳定的桶排序算法 * 因为addressArr存储的元素的下标，从后往前，对应下标逐个减少 */ while (i >= 0) { Node node = nodeList.get(i); temNodeList.set((addressArr[node.digitValue] - 1), node); addressArr[node.digitValue]--; i--; } // 更新arr数组 for (int h = 0; h < arr.length; h++) { arr[h] = temNodeList.get(h).realValue; } System.out.print("按一位排序的结果："); for (i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } } private static int getMaxDigit(int[] arr) { int digit = 0; int tem, temDigit; for (int i = 0; i < arr.length; i++) { tem = arr[i]; temDigit = 0; while (tem != 0) { temDigit++; tem = tem / 10; } if (temDigit > digit) { digit = temDigit; } } return digit; } /** * 获取某一位的值 * @param realValue 真正的值 * @param k 第几位 */ private static int getDigitValue(int realValue, int k) { // 首先判断有没有这么多位，没有则返回0 int tem = 1; int temK = k - 1; while (temK > 0) { tem = tem * 10; temK--; } if (realValue < tem) { return 0; } // 获取对应位数 temK = k - 1; while (temK > 0) { realValue /= 10; temK--; } return realValue % 10; } private static class Node { /** * 当前位的值 */ public int digitValue; /** * 真真的值 */ public int realValue; } public static void main(String[] args) { int[] arr = {342, 58, 576, 356}; baseSort(arr); System.out.print("最终结果: "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }
