我一直坚持这个问题，并希望有人会给出答案并解释 .
您将获得一个没有重复元素的未排序数组A，并要求按降序排序查找第K个最大元素 . 例如，如果A是数组[11,6,1,2,15,7,4,8,20]和K = 3，那么答案应该是[20,15,11] . 描述如何修改选择排序和heapsort来解决这个问题（两个单独的答案） . 作为N = A.length和K的函数，算法运行时间最差的是什么？
通常选择什么类型：
找到最高元素，换到第一名
找到下一个最高元素，交换到第二位
......
查找倒数第二个元素，交换到倒数第二个位置
完成 .
正常运行时间是 O(N * N) ，因为每个 N 步骤都是搜索问题，即 O(N) .
O(N * N)
N
O(N)
当你找到第一个K元素时，你可以停下来 . 如果你提前中止它，那就不再是N步了;但每一步都没有改变 .
所以大O.
因此，中止选择排序的>是O（K * N） .
堆排序分两步完成：heapify和siftdown . 必须正确完成Heapify（创建堆结构），它将保持不变 . 由于它在比siftdown更少的操作中执行，因此从heap sort的big-O中省略了它 .
Siftdown（将堆中的元素交换为排序数组）与选择排序非常非常相似，但是在每个 N 步骤中执行以查找下一个最高元素的操作更快： O(log N) .
O(log N)
由于siftdown几乎完全相同，从概念上讲，作为选择排序，你可以在发现前K个结果的同时中止它 .
这意味着大O.
因此，中止堆排序的>是O（K * log N） .
1 回答
通常选择什么类型：
找到最高元素，换到第一名
找到下一个最高元素，交换到第二位
......
查找倒数第二个元素，交换到倒数第二个位置
完成 .
正常运行时间是
O(N * N)，因为每个N步骤都是搜索问题，即O(N).所以大O.
因此，中止选择排序的>是O（K * N） .
堆排序分两步完成：heapify和siftdown . 必须正确完成Heapify（创建堆结构），它将保持不变 . 由于它在比siftdown更少的操作中执行，因此从heap sort的big-O中省略了它 .
Siftdown（将堆中的元素交换为排序数组）与选择排序非常非常相似，但是在每个
N步骤中执行以查找下一个最高元素的操作更快：O(log N).这意味着大O.
因此，中止堆排序的>是O（K * log N） .