Наиболее подходящий алгоритм сортировки

Question

Я должен отсортировать большой массив двойников размером 100000.

Дело в том, что я не хочу сортировать весь массив, а нахожу только самые большие 20000 элементов в порядке убывания.

В настоящее время я использую сортировку выбора. Есть ли способ улучшить производительность?

Answer 1

100 000 - не очень большой массив на большинстве современных устройств.Вы уверены, что не можете просто отсортировать их все, используя стандартную библиотечную функцию сортировки?

Вы можете избежать полной сортировки, используя вариант heapsort .Обычно в heapsort вы создаете кучу всего набора данных (100 000 элементов в вашем случае).Вместо этого, разрешается только увеличение кучи до 20000 элементов.Держите самый большой элемент в верхней части кучи.Когда куча заполнена (20 000 элементов), вы сравниваете каждый последующий элемент набора данных с вершиной кучи.Если следующий элемент набора данных больше, чем вершина кучи, просто пропустите его.Если он меньше вершины кучи, вставьте верх кучи и вставьте элемент из набора данных.

Как только вы пройдете весь набор данных, у вас будет куча из 20 000 наименьшихэлементы набора данных.Вы можете вытолкнуть их один за другим в массив, чтобы получить отсортированный массив.

Этот алгоритм выполняется за O (N log K), где N - размер набора данных (100 000 в вашем примере) и K - количество элементов, которое вы хотите сохранить (20 000 в вашем примере).

Answer 2

вы можете улучшить, используя Алгоритм быстрой сортировки для повышения его эффективности, или вы можете использовать сортировку слиянием, которая сделает это за время nlog (n). посчитайте время бега и найдите подходящий для вашего снарио.

Answer 3

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

Короче, просто замените "правосторонний" рекурсивный вызов на quicksort() на

if (pivot >= k) quicksort(...)

В качестве альтернативы вы можете следовать стандартному алгоритму heapsort , но остановиться после извлечения K элементов из кучи.

Оба этих подхода занимают время O (N + KlogN), пространство O (N) и могут быть выполнены на месте.

Answer 4

Я бы предложил начать с сортировки сегментов , а затем использовать некоторые из более простых алгоритмов для сортировки каждого сегмента. Если какой-либо из них все еще слишком велик, вы можете либо снова использовать сортировку по группам, либо другой метод nlog (n) (например, mergesort или quicksort). В противном случае выделение (или, лучше, вставка) подойдет просто так.

Только для сравнения: выбор / вставка / быстрая сортировка - O (n * n), сортировка слиянием - O (nlog (n)), сортировка сегментов - O (n * k), где k - количество сегментов. Выберите k

Примечание: наихудший сценарий быстрой сортировки - это O (n * n), но на практике это намного быстрее.

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

Answer 5

Если вы используете алгоритм пузырьковая сортировка и переместитесь влево на меньшее число, после 20 000-й итерации в конце массива будут наименьшие числа в порядке убывания.
Например, 3 7 2 5 1 4 8 массив:
1 итерация: 7 3 5 2 4 8 1
2 итерации: 7 5 3 4 8 2 1
3 итерации: 7 5 4 8 3 2 1

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