前言
Lucene 中对于选择算法，有两个实现，快速选择和基数选择.
上一篇文章讲了IntroSelector，这篇文章讲RadixSelector.
基数排序介绍
基数选择和基数排序非常类似，本文侧重点在于 Lucene 的实现，因此对于基数排序的详细原理就不解释了。
大概介绍下：
基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到 1887 年赫尔曼·何乐礼在打孔卡片制表机（Tabulation Machine）上的贡献 [1]。
它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。
实现原理的话比较好懂。快进到 Lucene 的代码。
org.apache.lucene.util.RadixSelector 源码分析
版本 8.7.0
带有注释的完整源码在：org.apache.lucene.util.RadixSelector 源码分析
因为org.apache.lucene.util.RadixSelector也是对Selector的实现，那么他的入口函数也是 select. 我们从 select 开始分析。
入口 select 方法
代码语言：javascript复制 @Override
// k, 就是 topk 的那个 k
public void select(int from, int to, int k) {
// check
checkArgs(from, to, k);
// 在这个范围上比较所有值
// k 使我们求的 topk 的 k
// 每个值从第 0 个字符开始比较
// 这是第一层的递归，用来检测递归太深了
select(from, to, k, 0, 0);
}
// 又他妈的是递归吗？？？？
// * @param d the character number to compare
// 开始比较的字符的编号，也就是 index
// * @param l the level of recursion
private void select(int from, int to, int k, int d, int l) {
// 如果数据很少了，或者已经递归的太多了，是不是就换个策略，不要再递归了呢
// 数据变窄了，超过递归深度了，就使用备用的选择算法
if (to - from <= LENGTH_THRESHOLD || d >= LEVEL_THRESHOLD) {
getFallbackSelector(d).select(from, to, k);
} else {
// 继续递归
radixSelect(from, to, k, d, l);
}
}可以看到，实现自接口的select方法只是简单的做了一个转发，之后进入重载的select方法。之后的逻辑就是一个条件语句。
如果to-from<100，或者递归层级大于 8 层, 就是用备选的选择算法（快速选择算法）. 否则调用radixSelect.
以内部分为猜想，尚未证实
为什么要限制层数呢
这个问题我开始也百思不得其解。源码中对于这个的注释是：after that many levels of recursion we fall back to introselect anyway this is used as a protection against the fact that radix sort performs worse when there are long common prefixes (probably because of cache locality)
我不明白为什么太长的公共前缀会导致性能变差，在实现时，我们完全可以直接跳过所有的公共前缀长度。
后来猜想，所谓的最坏情况，并不是所有元素都有一个很长的公共前缀，而是递增式的。
代码语言：javascript复制 a
a b
a b c
a b c d形如途中所示的数据，会导致 badcase.
- 当我们开始排序时，第一轮排序 a 全部一样，
- 第二轮是三个 b 和一个空。因此只有两个桶，一个桶是 1. 一个桶是 all -1. 相当于没怎么排序
- 第三轮和第二轮一样差劲。 这种情况就类似于快排里面的，每次都挑选到了最大的值。导致了最差劲的时间复杂度
但是对于快速选择算法，我们尚且有三者中位数法和中位数的中位数法来避免这一个问题，基数排序没有。因此只能设置阈值，当发现遇到了极端情况时，及时切换到快速选择算法上去。
radixSelect 方法
从方法的名字可以看出来，这是这个类的核心方法了。
流程图：
代码：
这个我看了好久。所以注释够多了。
核心流程：
- 计算公共前缀长度，构建当前字节的直方图
- 如果有公共前缀，则跳到该位进行计算
- 如果没有，则将直方图中 k 所在的桶进行递归运算。
就可以找到对应的第 K 位啦。
computeCommonPrefixLengthAndBuildHistogram 方法
这是另外一个值得一提的方法，它的功能是：
计算公共前缀，并填充直方图。
代码语言：javascript复制 /** Build a histogram of the number of values per {@link #getBucket(int, int) bucket}
* and return a common prefix length for all visited values.
* @see #buildHistogram */
// 构建一个每个桶的值的数量的直方图
// 返回所有值的公共前缀长度
// 这里的 k 变了， 这里的 k 是每个值从第 x 位开始比较
private int computeCommonPrefixLengthAndBuildHistogram(int from, int to, int k, int[] histogram) {
// 公共前缀
final int[] commonPrefix = this.commonPrefix;
// 所以刚开始认为公共前缀的长度， 要么是原有的，要么就是最大长度减去 k, 其实就是要比的除了 k 位之外的，都是公共前缀
// 这是估计出来的
int commonPrefixLength = Math.min(commonPrefix.length, maxLength - k);
for (int j = 0; j < commonPrefixLength; j) {
// 第一个元素的，k j 个字节
final int b = byteAt(from, k j);
// 公众前缀的数组，在这里其实等于等一个值的 k 位及以后
commonPrefix[j] = b;
// 说明第一个长度不够了。即第一个元素全放进去，还没到你预估的公共前缀长度。
// 说明你算错了，那么真正的公共前缀长度就是第一个元素的值
if (b == -1) {
commonPrefixLength = j 1;
break;
}
}
// 所有的事情都是从 k 位开始的， 因此之前的位都在以前的递归里面解决了。
// 上面是进行了假设，假设公共前缀是第一个值的 k 位及以后。
// 那么公共前缀长度就是 k 位以后的位数
// 公共前缀是从 k 位开始
int i;
// 这轮遍历，是数组上的全部遍历
// 不算第一个数，因为第一个数已经放到公共前缀里面了，大家都和他比较呢。
// 假设最后算出来的公共前缀是 3. 那么说明 k->k 3 这期间大家都一样。
outer: for (i = from 1; i < to; i) {
for (int j = 0; j < commonPrefixLength; j) {
// 这个我看不懂了啊
// 这里拿到第二个数字的 k 0 位，k 1 位之类
final int b = byteAt(i, k j);
// 去和公共前缀里面比较，公共前缀里面放的是第一个数字的对应的位
// 等于就好说，继续算公共前缀
// 不等于的话，就说明有某一个值的某一个位和第一个值的对应位置不一样了，那就不公共了。
if (b != commonPrefix[j]) {
// 公共前缀最长也只能有第一个值那么长
commonPrefixLength = j;
if (commonPrefixLength == 0) { // we have no common prefix
// 如果公共前缀长度为 0，那就没必要继续后面的操作了，
// 比如第二个值和第一个值完全不一样，那就说明不会有公共前缀了
// 如果所有的数字没有公共前缀，那么第一个值的第一位，有 i-from 个。
// 比如我计算到第 8 个的时候，发现大家完全没有公共前缀，但是我既然能到第 8 个。说明前面 7 个值的第一位肯定是一样
// 那么第一个值的第 k 位的个数就是 7
histogram[commonPrefix[0] 1] = i - from;
// 当前这个值的 k 为至少也有一个。我都遍历到这里了，当然有一个了。
histogram[b 1] = 1;
// 跳出，没有公共前缀，不算了
break outer;
}
// 如果公共前缀还不是 0，那就说明还有的玩。就继续下一个值来进行比较，一直到求到了真正的公共前缀
break;
}
}
}
// 上面是一个完整的算公共前缀的过程，要么算完，要么知道发现没有公共前缀
// 在计算的过程中，根据已有的信息，顺手写了一点点直方图。主要是写了第一位相同的有多少个。以及在我判断挂掉的那一瞬间，那个值有一个。
if (i < to) {
// the loop got broken because there is no common prefix
// 说明上面的循环是跳出了，所以应该没有公共前缀
assert commonPrefixLength == 0;
buildHistogram(i 1, to, k, histogram);
} else {
// 有公共前缀
assert commonPrefixLength > 0;
// 只要有公共前缀，那么第一个值的第 k 位，大家肯定都是一样的了
// 我就可以写这个第 k 位这个值，有 to-from 个一样的。
histogram[commonPrefix[0] 1] = to - from;
}
// 返回公共前缀的长度
return commonPrefixLength;
}代码的核心路径是：
- 将第一个值全部放在公共前缀里面，此时公共前缀就是第一个值
- 从第二个开始遍历，逐个字节开始与第一个值进行比较，如果遇到不相等的值，减少公共前缀的长度
- 根据是否有公共前缀，构建第 K 字节上的值的直方图，一个字节最大值是 256. 加上一个 null 值，直方图共 257 位。
- 返回公共前缀和直方图。
第 1，2 步骤，就是一个标准的多个字符串求最长公共前缀的算法，与其刷题，不如看源码，到处都是原题呢～.
思考题
在org.apache.lucene.util.RadixSelector.select(int, int, int, int, int)方法中，
private void select(int from, int to, int k, int d, int l) {
// 如果数据很少了，或者已经递归的太多了，是不是就换个策略，不要再递归了呢
// 数据变窄了，超过递归深度了，就使用备用的选择算法
if (to - from <= LENGTH_THRESHOLD || d >= LEVEL_THRESHOLD) {
getFallbackSelector(d).select(from, to, k);
} else {
// 继续递归
radixSelect(from, to, k, d, l);
}
}比较递归最大深度的时候，使用的是d而不是l. 这是正确的吗？
从注释上看，l 才是递归的深度。
d 过大并不会影响效率，而且 d 最终一定会很大。
这个值的错误，不会导致编译错误，或者程序结果错误。甚至都不会导致性能极度变差。
那么他导致的是什么呢？导致的是，很多本可以在基数选择的 O(3n) 的时间复杂度下解决的问题，被放到了快速选择的 O(5n) 下去解决。
导致的是平均的线性时间复杂度的常量变大了。
这是我的猜测，我也不知道对不对，还在思考哈哈哈哈。
参考文章
https://zh.wikipedia.org/wiki/基数排序
完。
以上皆为个人所思所得，如有错误欢迎评论区指正。
欢迎转载，烦请署名并保留原文链接。
更多学习笔记见个人博客或关注微信公众号 < 呼延十 >——>呼延十
