Method 1
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.
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.
This takes n-k+1 compares exactly.
Now the winner of these n-k+2 cannot be your kth largest element. Consider its path P up the tournament.
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.
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.
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.
Method 2
As an alternative, you can maintain a min-heap of k elements.
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.
At the end, the heap will contain the top k elements. This will take O(n log k)
compares.
Of course, if n is small, just sorting the array should be good enough. The code will be simpler too.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…