假设我想在n个元素的数组中找到K最大值，并在排序输出中返回它们。k可能是-
k = 30 , k = n/5 ..
我想了一些有效的算法，但我能想到的只是O（nlogn）的复杂性。我能用`O（n）做吗？也许可以快速修改一下？
谢谢！
这个问题可以在中使用基于最小堆的优先级队列来解决
O(NlogK) + (KlogK) time
如果k是常数(k=30 case)，则复杂度等于O（N）。
如果k=O（N）（k=n/5 case)），则复杂度等于O（NlogN）。
常数k-k选择算法的另一个选择基于平均时间为O（N）的快速排序分区（而最坏的情况可能发生O（N^2））
如果假设只想对整数进行排序，那么有一种方法可以对接近O（n）的元素进行排序。这可以通过像Bucket Sort或Radix Sort这样的算法来实现，它们不依赖于两个元素之间的比较（限制为O（n*log（n）））。
然而，请注意，这些算法也有最坏的运行时间，可能比O（n*log（n））慢。
更多信息可以在这里找到。
没有任何基于比较的排序算法可以实现比O（n*lg n）更好的平均案例复杂度
有很多论文都有校样，但这个网站提供了一个很好的视觉例子。
因此，除非给你一个排序数组，否则你的最佳情况将是O（n-lgn）算法。
有基数和桶之类的排序，但它们并不像标题所暗示的那样基于比较排序。