我有一个n个浮点数组，我想返回前k个
(在我的情况下，n〜100，k〜10)
是否有已知的最佳解决方案来解决此问题？
有人可以提供C算法吗？
编辑:实际上这里有两个问题:已排序和未排序。我对未排序感兴趣，应该更快一些!
最佳答案
方法1
由于k很小，因此您可以使用锦标赛方法找到第k个最大值。 Knuth的《编程艺术》，第3卷，第212页中介绍了此方法。
首先在n-k + 2个元素上创建一个锦标赛。像 knockout 网球比赛。首先，将您分成两对，并比较两对的成员(好像这两对进行了比赛而一个输了)。然后是赢家，您又分成几对，依此类推，直到有赢家为止。您可以将其视为一棵树，获奖者位于顶部。
这需要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)内存。
就比较次数而言，这可能胜过任何选择算法。
方法2
或者，您可以保持k个元素的最小堆。
首先插入k个元素。然后，对于数组的每个元素，如果它小于堆的min元素，则将其丢弃。否则，请删除堆的min并从数组中插入元素。
最后，堆将包含前k个元素。这将需要O(n log k)进行比较。
当然，如果n小，仅对数组进行排序就足够了。代码也会更简单。