排列算法的K个最大元素

Question

我一直在这个问题上停滞不前，希望有人会给出答案，并请解释。

给出一个没有重复元素的未整理的整数数组A，并要求按降序排列的次序查找最大元素Kth 。例如，如果A是数组[11,6,1,2,15,7,4,8,20]和 K = 3，那么答案应该是[20,15,11]。描述你将如何修改选择排序和解决这个问题（两个单独的答案）。作为N = A.length和K的函数，你的 算法的最差情况运行时间是多少？

Answer 1

什么选择排序一般不会：

• 查找最高的元素，交换第一名
• 查找下一个最高的元素，交换到第二位
• ...
• 找到第二TO-最后一个元素，交换到倒数第二位
• 完成。

正常运行时间为O(N * N)，因为每个的N步骤是搜索问题，这是O(N)。

当您找到第一个K元素时，您可以停下来。如果你提早放弃它，它不再是N步骤;但每一步都不变。

并且因此大O

中止选择排序的

因此O(K * N)。

堆排序分两步完成：heapify和siftdown。 Heapify（创建堆结构）必须正确完成，并保持不变。由于它的执行次数少于siftdown，所以它在堆排序的big-O中被省略。 Siftdown（将堆中的元素从堆中交换到排序后的数组）非常类似于选择排序，但在N步骤中执行的每个步骤中执行的操作更快：O(log N)。

由于siftdown做几乎同样的事情，在概念上，作为选择的排序，你可以说，除了立即中止，因为它已经找到前K结果。

这意味着大O

中止堆排序的

因此O(K * log N)。