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