arrays - 数组的K个最大元素，排序算法

Question

我一直被这个问题困住，希望有人能给出答案并解释一下。

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

Answer 1

选择排序通常做什么:

• 找到最高的元素，交换到第一位
• 找到下一个最高元素，交换到第二位
• ...
• 找到倒数第二个元素，交换到倒数第二个位置
• 完成。

正常运行时间是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)。