Какой алгоритм сортировки обеспечивает наилучшую производительность в худшем случае?

Question

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

Answer 1

убедитесь, что вы видели это:

визуализация алгоритмов сортировки - это помогло мне решить, какой тип алгоритма использовать.

Answer 2

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

Answer 3

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

HeapSort хорош, если все ваши данные помещаются в память, тогда как MergeSort позволяет лучше выполнять сортировку на диске (но в целом занимает больше места).

На странице алгоритма сортировки Wikipedia упоминаются другие менее известные алгоритмы, которые имеют O (n log n) в худшем случае. (по комментарию от mmyers)

Answer 4

для человека с неограниченным бюджетом

Шутливо, но верно: Сортировка сетей Торговое пространство (в натуральном выражении) для лучшей сортировки, чем O (n log n)!

Не прибегая к такому оборудованию (которое вряд ли будет доступно), у вас есть нижняя граница для лучших сортов сравнения O (n log n)

O (n log n) производительность в худшем случае (без определенного порядка)

• Сортировка бинарных деревьев
• Сортировка слиянием
• Сортировка кучи
• Плавная сортировка
• Intro Sort

Избиение журнала n

Если ваши данные поддаются ему, вы можете преодолеть ограничение n log n, но вместо этого позаботьтесь о количестве битов во входных данных

Radix и Bucket , вероятно, являются наиболее известными примерами этого. Без дополнительной информации о ваших конкретных требованиях было бы бесполезно рассматривать их более подробно.

Answer 5

Если у вас есть гигантский набор данных (т. Е. Намного больше, чем доступная память), вы, вероятно, храните данные на диске / ленте / что-то с дорогим случайным доступом, поэтому вам нужна внешняя сортировка.

В этом случае сортировка слиянием работает хорошо; в отличие от большинства других видов, он не предполагает случайного чтения / записи.

Answer 6

Быстрая сортировка обычно самая быстрая, но если вам нужно хорошее время для худшего случая, попробуйте Heapsort или Mergesort . Они оба имеют O(n log n) худшее время.

Answer 7

Это зависит как от типа данных, так и от типа ресурсов. Например, есть параллельные алгоритмы, которые превосходят Quicksort, но, учитывая, как вы задали вопрос, маловероятно, что вы имеете к ним доступ. Бывают случаи, когда «наихудший случай» для одного алгоритма является «наилучшим случаем» для другого (почти отсортированные данные проблематичны для Quick и Merge, но быстро для гораздо более простых методов).

Answer 8

Если у вас достаточно большой набор данных, вы, вероятно, смотрите на сортировку отдельных блоков данных, а затем на сортировку слиянием для объединения этих блоков. Но в данный момент мы говорим, что наборы данных достаточно велики, чтобы быть ОЧЕНЬ больше, чем основная память.

Полагаю, самый правильный ответ будет "это зависит".

Answer 9

Зависит от размера в соответствии с Big O обозначением O (n) .

Вот список алгоритмов сортировки Лучший и худший случай для сравнения. Я предпочитаю 2 способа MergeSort

Answer 10

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

Целые книги написаны на алгоритмах поиска / сортировки. Вы не найдете «самый быстрый», предполагающий сценарий наихудшего случая, потому что разные виды имеют разные наихудшие ситуации.