基数排序原理及实战
基数排序
原理
我们来看这样一个排序问题。假设我们有 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] + " ");
}
}
}