我有一个包含 n 个 double 值的列表，我需要在该列表中找到 k 个最低的 double 值
- k 远小于 n
- 具有 n 个 double 值的初始列表是随机排序的
- 找到的 k 个最低的 double 值不需要排序
你会推荐什么算法？
目前我使用Quicksort 对整个列表进行排序，然后从排序后的列表中取出前k 个元素。我希望应该有一个更快的算法。
感谢您的帮助!!!
最佳答案
您可以为您的解决方案建模以匹配 nlargest() code in Python's standard library .
- 在最大堆上堆放前 k 个值。
- 迭代剩余的 n - k 个值。
- 将每个元素与堆顶部的元素进行比较。
- 如果新值较低，则执行heapreplace操作(用新值替换最顶层的堆元素，然后向下筛选)。
该算法的效率出奇地高。例如，当 n=100,000 且 k=100 时，对于随机排列的输入，比较次数通常约为 106,000 次。这只是略多于 100,000 次比较才能找到一个最小值。而且，它在整个数据集上进行的比较比完全快速排序少大约 20 倍。
研究和总结各种算法的相对强度:http://code.activestate.com/recipes/577573-compare-algorithms-for-heapqsmallest
关于c++ - 搜索算法以查找列表中的 k 个最小值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11407114/