Найдите самые большие 10% чисел в массиве в порядке

Очень глупый вопрос, просто отсортируйте его с помощью любого алгоритма сортировки и возьмите первые N / 10 элементов.

Алгоритм-2 эквивалентен выполнению этого с помощью сортировки кучи

Создайте кучу с стоимостью замещения O (lnN), заполненную первыми n / 10 элементами. Просканируйте оставшиеся числа, сравнивая с наименьшим значением в куче. Если значение текущего элемента выше, чем наименьший элемент в куче, вставьте его в кучу и удалите наименьший элемент. В худшем случае две операции O (lnN), умноженные на N отсканированных элементов, дают O (N ln N), что не лучше по времени, чем сортировка, но требует меньше памяти, чем сортировка всего, так что на практике, вероятно, будет быстрее (особенно, если N элементов не помещаются в кеш, но будет n / 10 - асимптотическое время имеет значение только тогда, когда вы находитесь в плоском пространстве).

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

, если это было возможно, вы могли бы полностью отсортировать массив в O (n * log (n)). (найдя отсортированные верхние 10% в массиве, который вы хотите полностью отсортировать, удалив их и повторяя этот процесс 10 раз).

поскольку сортировка невозможна при O (n * log (n)), это проблема.

Алго-1: Сортировка выделения будет выполняться за O (n ^ 2). Первое сканирование, которое вы выполняете (n-1), сравнивает, второй раз (n-2), время n / 10 (nn / 10), поэтому (n-1) + (n-2) + ... + (nn / 10) => O (n ^ 2)

Алгоритм-2: Удаление максимального элемента из кучи - это O (log n), поэтому этот будет запускать O (n log n), так как вы хотите удалить n / 10 элементов.

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

1. Выберите опорную точку
2. Отсканируйте все элементы и поместите их в один из двух сегментов: те, которые меньше опорного (левый сегмент), и те, которые больше, чем опорный сегмент (правый сегмент) (n-1) сравнения. Следуйте быстрой процедуре сортировки по замене на месте.

3. а. Размер ведра справа == n / 10: Готово.

   б. Размер корзины справа> n / 10, тогда новый список - это корзина справа, рекурсивно перейдите к шагу 1 с новым списком.

   c. Размер корзины справа

Если вы знаете N, просто создайте массив длиной 1/10 от него. начальное значение для каждой ячейки - Int.MinValue. Изучите каждое число в массиве. Если оно больше наименьшего числа в десятипроцентном массиве, добавьте его.

Избегает сортировки, но за счет постоянного сканирования массива ответов. Вы можете немного компенсировать это, сохраняя его в отсортированном порядке, чтобы вы могли использовать двоичный поиск.

Самым быстрым решением является использование алгоритма выбора на основе разделов , который выполняется в O (n) . Он основан на идее быстрой сортировки, за исключением того, что вместо рекурсивной сортировки обоих разделов вы переходите только к одному из разделов, чтобы найти k-й наименьший элемент.

Нахождение самых больших 10% достигается путем поиска k = (90% * N) -го наименьшего числа.

Если вы вспомните, как работает разбиение в быстрой сортировке, элементы ниже точки поворота перемещаются влево, а остальные элементы - вправо. Допустим, вы хотите выбрать k-й наименьший элемент. Затем вы видите, есть ли по крайней мере k элементов слева от точки поворота. Если да, то вы знаете, что можете игнорировать элементы в правом разделе. В противном случае вы можете игнорировать все элементы в левом разделе, потому что вы знаете, что этот элемент будет в правом разделе.

Обратите внимание, что алгоритм выбора определяет только эти 10% лучших. Если вам нужно, чтобы они были отсортированы, вы должны отсортировать эти числа (но только эти числа, остальные 90% можно игнорировать).

Я бы использовал быструю сортировку по убыванию по массиву и получил бы первые N / 10 элементов.

Наиболее эффективным алгоритмом было бы использование модифицированного быстрая сортировка.

Быстрая сортировка начинается с выбора «среднего» значения и помещения всех значений ниже этого слева и все больше справа. Обычно вы должны пойти вниз и рекурсивно отсортировать обе стороны, но вам нужно только отсортировать правую сторону, если слева меньше 10% элементов.

Если их больше 10%, то вам нужно отсортировать только левую часть и, вероятно, только часть левой.

Это не снизит сложность ниже оптимального O (N lg N), но уменьшит постоянный коэффициент и сделает его быстрее, чем очевидный подход «быстрая сортировка с выбором первых 10».