我有一个包含 n 个浮点的数组，我希望返回前 k 个
（在我的例子中，n ~ 100，k ~ 10）
该问题是否有已知的最佳解决路径？
谁能提供一个C算法吗？
编辑：实际上这里有两个问题：排序和未排序。我对未排序感兴趣，这应该更快！
Method 1
由于k很小，因此可以使用锦标赛方法来找到第k大的。此方法在 Knuth 的《编程艺术》第 3 卷第 212 页中进行了描述。
首先创建一个关于 n-k+2 个元素的锦标赛。就像网球淘汰赛一样。首先，您分成两人一组并比较各对的成员（就好像这两个人打了一场比赛，其中一个输了）。然后是获胜者，你们再次分成两人一组，依此类推，直到产生获胜者。您可以将其视为一棵树，获胜者位于顶部。
这需要 n-k+1 次比较。
现在这n-k+2的获胜者不可能是你的第k大元素。考虑一下它在锦标赛中的路径 P。
现在从剩下的 k-2 个中选择一个，然后沿路径 P 前进，这将为您提供一个新的最大值。基本上，您可以重做锦标赛，将前一个获胜者替换为 k-2 元素之一。令 P 为新获胜者的路径。现在从 k-3 中选择另一个并沿着新路径向上，依此类推。
最后，在您耗尽 k-2 后，将最大的替换为 -infinity，并且锦标赛中最大的将是第 k 大。你扔掉的元素是前k-1个元素。
这最多需要n - k + (k-1) [log (n-k+2)]比较以找到前 k 个。但它使用 O(n) 内存。
就比较次数而言，这可能会击败任何选择算法。
Method 2
作为替代方案，您可以维护一个包含 k 个元素的最小堆。
首先插入k个元素。然后对于数组的每个元素，如果小于堆的最小元素，则将其丢弃。否则，删除堆的最小值并从数组中插入元素。
最后，堆将包含前 k 个元素。这将需要O(n log k)比较。
当然，如果n很小，只需对数组进行排序就足够了。代码也会更简单。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
