K наибольшие элементы массива, алгоритм сортировки

Question

Я застрял в этой проблеме и надеялся, что кто-то даст ответы и объяснит, пожалуйста.

Вам предоставляется несортированный массив A из целых чисел без повторных элементов и попросил найти самые большие элементы Kth в порядке сортировки по убыванию. Например, если A - это массив [11,6,1,2,15,7,4,8,20] и K = 3, тогда ответ должен быть [20,15,11]. Опишите, как вы можете изменить сортировку сортировки и heapsort для решения этой проблемы (два отдельных ответа). Какое худшее время работы ваших алгоритмов , как функция N = A.length и K?

Answer 1

Какой выбор рода обычно делает:

• Найти высокий элемент, обмен на первое место
• Найти следующий самый высокий элемент, обмен на второе место
• ...
• Найти второй-to последний элемент, своп во второе-последнее место
• Выполнено.

Нормальное время бега O(N * N), потому что каждый из N шагов поиска проблема, которая O(N).

Вы можете просто остановиться, когда найдете первые элементы K. Если вы прервите его раньше, это уже не N шагов; но каждый шаг не изменился.

и так большой-O

из несостоявшегося выбора сорта, таким образом, O(K * N).

Куча сортировки выполняется в два этапа: heapify и siftdown. Heapify (создание структуры кучи) должно выполняться правильно, и оно останется неизменным. Так как он выполняется в меньшем количестве операций, чем siftdown, он опускается из большого размера сокета.

Siftdown (замена элементов из кучи в отсортированный массив) очень похож на сортировку, но операция, выполняемая в каждом из N шагов, чтобы найти следующий самый высокий элемент быстрее: O(log N).

Поскольку siftdown делает почти то же самое, концептуально, как выбор вид, вы можете прервать, что так же, как только он нашел лучшие K результатов.

Это означает, что биг-O

из несостоявшегося кучи рода, таким образом O(K * log N).