搜索算法查找列表中的 k 个最低值（选择算法/问题）

Question

我有一个包含 n 双精度值的列表，我需要找到该列表中的 k 最低双精度值

• k 比 n
小得多
• 具有 n 双值的初始列表是随机排序的
• 找到的 k 最低双精度值不需要排序

您会推荐什么算法？

目前，我使用 Quicksort 对整个列表进行排序，然后从排序列表中取出前 k 元素。我希望应该有一个更快的算法。

谢谢您的帮助！！！

Answer 1

您可以对解决方案进行建模以匹配 Python 标准库中的 nlargest() 代码。

• 堆化最大堆上的前 k 值。
• 迭代剩余的 n - k 值。
• 将每个元素与堆顶部的元素进行比较。
• 如果新值较低，则执行 heapreplace 操作（用新值替换最顶层的堆元素，然后向下筛选）。

该算法的效率出奇地高。 例如，当 n=100,000 且 k=100 时，对于随机排列的输入，比较次数通常约为 106,000 次。 这仅需要略多于 100,000 次的比较即可找到单个最小值。 而且，它对整个数据集进行的比较比完整快速排序少大约二十倍。

研究和总结各种算法的相对强度：http://code.activestate.com/recipes/577573-compare-algorithms-for-heapqsmallest

Answer 2

您可以使用选择算法找到第k个最低元素，然后迭代并返回它以及所有低于它的元素。如果列表可以包含重复项，则必须完成更多工作（确保最终不会出现更多所需的元素）。
这个解决方案是

O(n)

。 选择算法在 C++ 中实现为

nth_element()

另一种替代方法是 使用大小为 k 的最大 堆

，并迭代元素，同时维护堆以容纳所有 k 个最小元素。

for each element x:
   if (heap.size() < k):
      heap.add(x)
   else if x < heap.max():
      heap.pop()
      heap.add(x)

完成后 - 堆包含 k 个最小元素。
这个解决方案是

O(nlogk)

Answer 3

看一下 C++ 标准库中的 partial_sort 算法。

Answer 4

您可以使用std::nth_element。这是 O(N) 复杂度，因为它不对元素进行排序，它只是对它们进行排列，使得某个 N 下的每个元素都小于 N。

Answer 5

您可以使用选择排序，它需要 O(n) 来选择第一个最低值。一旦我们在位置 1 设置了最低值，我们就可以重新扫描数据集以找出第二低值。直到我们得到第 k 个最低值。这样，如果 k 比 n 足够小，那么我们将得到复杂度 kn ，相当于 O(n)...