選擇比較算法以查找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

回答