由网友(他是光芒亦能暖心i)分享简介：我有n个float数组，我想返回的前k个（在我的情况下，N〜100，K〜10）I have an array of n floats, and I wish to return the top k(in my case n ~ 100, k ~ 10)是否存在已知的最优解的路径对于这个问题？Is there...

我有n个float数组，我想返回的前k个 （在我的情况下，N〜100，K〜10）

I have an array of n floats, and I wish to return the top k (in my case n ~ 100, k ~ 10)

是否存在已知的最优解的路径对于这个问题？

Is there a known optimal solution path for this problem?

有人能提供一个C算法？

Could someone provide a C algorithm?

编辑：实际上这里有两个问题在这里：分类和排序的。我感兴趣的无序，这应该是快！

actually there are two problems here: sorted and unsorted. I am interested in unsorted, which should be faster!

推荐答案

方法1

由于k小，你可以用比赛的方法来找到第k个最大的。这种方法在编程，第3卷，第212 Knuth的艺术描述。

Since k is small, you can use the tournament method to find the kth largest. This method is described in Knuth's Art of Programming, Volume 3, Page 212.

首先，创建于N-K + 2元素的比赛。像淘汰赛网球赛事。首先分成对并比较对的成员（如如果这两个方面发挥了匹配和一个丢失）。然后获奖者，拆分到对再等等，直到你有一个赢家。你可以把它看作一棵树，用胜利者的顶部。

First create a tournament on n-k+2 elements. Something like a knockout tennis tournament. First you split into pairs and compare the members of the pairs (as if those two played a match and one lost). Then the winners, you split in to pairs again and so on, till you have a winner. You can view it as a tree, with the winner at the top.

这需要N-K + 1完全比较。

This takes n-k+1 compares exactly.

现在这些N-K + 2的胜者不能成为你的第k个最大的元素。考虑其路径P了比赛。

Now the winner of these n-k+2 cannot be your kth largest element. Consider its path P up the tournament.

剩余的K-2现在选择一个，并遵循了路径P，这将给你一个新的大。排序基本上你重做了previous冠军被替换为K-2的元素之一的比赛。设P为新冠军的道路。现在从K-3选择另一个，并按照新的路径和等。

Of the remaining k-2 now pick one, and follow that up the path P which will give you a new largest. Basically you sort of redo the tournament with the previous winner being replaced by one of the k-2 elements. Let P be the path of the new winner. Now pick another from the k-3 and follow the new path up and so on.

在你用尽K-2后，更换了比赛的最大与负无穷大和最大的将是第k个最大的结束。你扔掉的元素是顶部的K-1的元素。

At the end after you exhaust the k-2, replace the largest with -infinity and the largest of the tournament will be the kth largest. The elements you have thrown away are the top k-1 elements.

这需要至多 N - K +（K-1）的log（n-K + 2）] 的比较，找到前k个。它使用O（n）的内存，但。

This takes at most n - k + (k-1) [log (n-k+2)] comparisons to find the top k. It uses O(n) memory though.

在数量方面的比较，这应该有可能击败任何选择算法。

In terms of number of compares this should likely beat any selection algorithms.

方法2

作为一种替代方法，可以保持最小堆k个元素的。

As an alternative, you can maintain a min-heap of k elements.

首先插入k个元素。然后对数组的每个元素，如果是小于堆的最小元素，把它扔掉。否则，删除最小堆，并从阵列插入的元素。

First insert k elements. Then for each element of array, if it is less than the min element of the heap, throw it away. Otherwise, delete-min of the heap and insert the element from the array.

目前结束时，堆将包含顶部k个元素。这将需要 O（N日志K）进行比较。

At the end, the heap will contain the top k elements. This will take O(n log k) compares.

当然，如果n很小，只是排序数组要足够好。在code会更简单了。

Of course, if n is small, just sorting the array should be good enough. The code will be simpler too.