海量无序数据寻找第 K 大的数

发布时间：2025-11-05 07:58:31 来源：码上建站 作者：系统运维

本文转载自微信公众号「Kirito的海量技术分享」，作者kiritomoe。无序转载本文请联系Kirito的数据数技术分享公众号。

简单抽象一下问题，寻找便是海量今天的主题：在一个百万级无序的 long 数组中，寻找第 K 大的无序数。要求当然是数据数越快找到越好。

top K 问题

题面一描述出来，寻找很多人都会联想到 top K 问题，海量这道题无论是无序算法领域还是工程领域，都讨论的数据数极其广泛，并且在实际项目中也很容易会遇到类似的寻找问题，我也正好趁着这个机会总结成一篇文章。海量

常见的无序 top K 问题，及其变种：

传统 top K 问题的描述：

在海量数据中找出最大的前 K 个数

注意我这次提出的问题和传统 top K 有一点区别，传统的 top K 问题要求的一般是”前 K 大的数“，而我现在遇到的是”第 K 大的数“。区别要说大也不大，但对于我们最终选择的方案可能会有很大的区别。

我下面会介绍一些传统的 top K 问题的解决思路。站群服务器并且，按照我一贯的风格，肯定会有代码放出来，你如果是为了寻找一个”海量无序数据寻找第 K 大的数“问题的答案，相信你可以直接 copy 我的代码。

方案一：排序法

排序法是最容易想到的思路，复杂度为 O(nlogn) 。能够想到的各类排序算法呼之欲出，快速排序、归并排序、插入排序、猴子排序...etc

但是工程领域选择方案，往往不能仅仅使用算法复杂度来评估：

那这个时候有人就要问了，我该如何选择合适的方案呢?哎，那我又要提到那句话了，benchmark everything!虽然你肯定知道我最终没有选择使用排序来解决第 K 大的问题，但我还是想分享给你我的一些测试结论。

在 100w~1000w 数据量级别的无序 long 数组中，JDK 自带的 Array.sort() 比任何一个排序方案都要快。

Array.sort 的内部实现为 timsort，是一种优化过后的归并排序。

排序单纯靠想也知道不是最优的方案，因为我提出的问题中，仅仅需要找到第 K 大的数，排序方案却兴师动众把整个数组理顺了，没必要。

方案二：堆

针对一般的 top K 问题，一般都会默认 K 很小，所以一般的 top K 问题，可以选择使用堆来解决。

堆有个重要的性质：每个结点的值均不大于其左右孩子结点的值，则堆顶元素即为整个堆的最小值。JDK 中 PriorityQueue 实现了堆这个数据结构堆，通过指定 comparator 字段来表示小顶堆或大顶堆，默认为自然序(natural ordering)。

小顶堆解决 Top K 问题的思路：小顶堆维护当前扫描到的最大 K 个数，其后每一次扫描到的元素，若大于堆顶则入堆，然后删除堆顶;依此往复，直至扫描完所有元素。Java 实现第 K 大整数代码如下：

回到我遇到的问题，求第 K 大的数，这里没有说明 K 的范围，那么最坏情况下，K == N/2，无论维护一个 top K 的小顶堆还是维护一个 top(N - K) 的大顶堆，都需要占用 O(N/2) 的内存，而对于海量数据而言，这显示是一笔非常大的开销。所以针对我比赛的场景，堆的方案可以直接 pass。

堆的解法适用于 K 较小的场景，而且非常方便维护前 K 个数。

方案三：Quick Select

Quick Select 你可能没听过，但快速排序(Quick Sort)你肯定有所耳闻，其实他们两个算法的作者都是 Hoare，并且思想也非常接近：选取一个基准元素 pivot，将数组切分(partition)为两个子数组，比 pivot 大的扔左子数组，比 pivot 小的扔右子数组，然后递推地切分子数组。Quick Select 不同于 Quick Sort 之处在于其没有对每个子数组做切分，而是对目标子数组做切分。其次，Quick Select 与Quick Sort 一样，是一个不稳定的算法;pivot 选取直接影响了算法的好坏，最坏情况下的时间复杂度达到了 O(n2)。

在大学参加 ACM 时，我便第一次接触了该算法，记得那时数据量正好卡的 Quick Sort 无法通过，Quick Select 可以通过。

Quick Select 的 Java 实现如下：

最终，我选择使用了方案三：Quick Select 作为我求解第 K 大数的方案，也是 benchmark 下来最快的方案。在 10 次查询中，排序方案耗时为 6s，而 Quick Select 方案，仅需要 300ms，可以说是非常大的优化。

总结

本文简单介绍了无序数组求 Top K 问题和无序数组求第 K 大数字两类非常相似的问题，并且提供了常见的三种解决方案。当然，该问题也有很多变种，例如在多核机器，多主机上求解 TopK，甚至可以引入外排和 MapReduce 的思想，其实已经是在考虑其他层面的优化了，我在这里就不过多阐释了。

相关文章