Когда каждый сортирует используемый алгоритм? [закрытый]
Каковы варианты использования, когда конкретный алгоритм сортировки предпочтен по другим - сортировка слиянием по сравнению с QuickSort по сравнению с пирамидальной сортировкой по сравнению с 'вводным видом' и т.д.?
Существует ли рекомендуемое руководство в использовании их на основе размера, типа структуры данных, доступной памяти и кэша и производительности ЦП?
4 ответа
Во-первых, определение, поскольку оно довольно важно: стабильная сортировка - это такая, которая гарантированно не меняет порядок элементов с одинаковыми ключами.
Рекомендации:
Быстро sort: Когда вам не нужна стабильная сортировка и производительность в среднем случае важнее, чем производительность в худшем случае. Быстрая сортировка - это в среднем O (N log N), в худшем случае - O (N ^ 2). В хорошей реализации используется вспомогательная память O (log N) в виде пространства стека для рекурсии.
Сортировка слиянием: Когда вам нужна стабильная сортировка O (N log N), это единственный вариант. Единственным недостатком этого является то, что он использует дополнительное пространство O (N) и имеет немного большую константу, чем быстрая сортировка. Есть несколько сортировок слияния на месте, но, AFAIK, все они либо нестабильны, либо хуже, чем O (N log N). Даже у сортировок O (N log N) на месте константа намного больше, чем у простой старой сортировки слиянием, что они скорее теоретические курьезы, чем полезные алгоритмы.
Сортировка кучи: Когда вам не нужна стабильная сортировка, и вы больше заботитесь о производительности в худшем случае, чем о средней производительности. Гарантированно он равен O (N log N) и использует вспомогательное пространство O (1), что означает, что у вас не будет неожиданно закончиться место в куче или стеке на очень больших входных данных.
Introsort: Это быстрая сортировка, которая переключается на сортировку по куче после определенной глубины рекурсии, чтобы обойти наихудший случай быстрой сортировки O (N ^ 2). Это почти всегда лучше, чем простая старая быстрая сортировка, поскольку вы получаете средний случай быстрой сортировки с гарантированной производительностью O (N log N). Вероятно, единственная причина использовать сортировку кучи вместо этого - в системах с жесткими ограничениями памяти, где пространство стека O (log N) практически значимо.
Сортировка вставкой : когда N гарантированно мало, в том числе как базовый вариант быстрой сортировки или сортировки слиянием. Хотя это O (N ^ 2), она имеет очень маленькую константу и является стабильной сортировкой.
Пузырьковая сортировка, сортировка по выбору : Когда вы делаете что-то быстрое и грязное и по какой-то причине можете ' t просто используйте алгоритм сортировки стандартной библиотеки. Единственное преимущество, которое они имеют перед сортировкой вставкой, - это немного проще реализовать.
Сортировка без сравнения: При некоторых довольно ограниченных условиях можно преодолеть барьер O (N log N) и выполнить сортировку за O (N) . Вот несколько случаев, когда это стоит попробовать:
Подсчетная сортировка:
Быстрая сортировка обычно в среднем самая быстрая, но в худшем случае она ведет себя довольно неприятно. Поэтому, если вы должны гарантировать, что плохие данные не дадут вам O (N ^ 2) , вам следует избегать этого.
Сортировка слиянием использует дополнительную память, но особенно подходит для внешней сортировки ( т.е. огромные файлы, которые не помещаются в память).
Heap-sort может выполнять сортировку на месте и не имеет квадратичного поведения наихудшего случая, но в большинстве случаев медленнее, чем быстрая сортировка.
Там, где задействованы только целые числа из ограниченного диапазона, вы можете использовать какую-нибудь сортировку по основанию, чтобы сделать это очень быстро.
В 99% случаев вас устроят библиотечные сортировки, которые обычно основаны на быстрая сортировка.
На странице Википедии об алгоритмах сортировки есть отличная сравнительная таблица.
http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms
То, что предоставленные ссылки на сравнения / анимации не учитывают, - это когда объем данных превышает доступную память --- в этот момент количество проходов по данным, т.е. / O-затраты доминируют во время выполнения. Если вам нужно это сделать, прочтите «внешнюю сортировку», которая обычно охватывает варианты сортировки слиянием и кучей.
http://corte.si/posts/code/visualisingsorting/index.html и http://corte.si/posts/code/timort/index.html также есть несколько интересных изображений, сравнивающих различные алгоритмы сортировки.