选择比较算法以查找k最大值

假设我想要在n个元素的数组中找到K max值，并且还将它们返回到排序后的输出中。 k可以是 -选择比较算法以查找k最大值

k = 30 , k = n/5 ..

我想到了一些有效的算法，但所有我能想到的是O（nlogn）的复杂性。我可以在O（n）中做到吗？也许有一些快速排序的修改？

谢谢！

2016-05-12 Barak Mi

问题可能使用基于最小堆优先级队列中

O(NlogK) + (KlogK) time

如果k恒定(k=30 case)得到解决，则复杂度等于O（N）。

若k = O（N）（k=n/5 case)，那么复杂性是等于O（NlogN）

为常数k的另一种选择。 - K-select algorithm基于快速排序分区与平均时间为O（N）（而最坏的情况下O（N^2）可能发生）

2016-05-13 05:55:18 MBo

只是为了更好地理解 - 如果我的输入是n的根 - 仍然我的复杂度是O（Nlogn）？ –

如果k〜= Sqrt（N） - 是。（N^1/2））= O *（N * 0.5 * log（N））= O（Nlog（N））' – MBo

为什么不应该第一个N还= N^1/2？ N = 1/2 * log（N^1/2））？ –

如果您假设您只想对整数进行排序，则可以在几乎O（n）中对元素进行排序。这可以用像Bucket Sort或Radix Sort这样的算法来完成，它不依赖于两个元素之间的比较（限于O（n * log（n）））。

但是请注意，这些算法也有最坏情况下的运行时间，可能比O（n * log（n））慢。

更多的信息可以是found here。

2016-05-12 20:48:49

没有比较基础排序算法可以实现比Ø更好的平均情况复杂度（N * LG N）

没有与证据在那里多篇论文，但this网站提供了不错的视觉例子。

所以，除非给出一个排序数组，否则最好的情况是O（n lg n）算法。

有几种像基数和桶，但它们不是基于比较的排序，就像你的标题似乎暗示的那样。

2016-05-12 20:53:27 tt9

回答