Сортировка Сортировка сортировки, по-видимому, имеет наихудшую сложность O (nlogn) и использует O (1) пространство для операции сортировки.
Это кажется лучше, чем большинство алгоритмов сортировки. Тогда почему бы не использовать Heap Sort всегда как алгоритм сортировки (и почему люди используют механизмы сортировки, такие как сортировка Merge или Quick sort)?
Кроме того, я видел, как люди используют термин "нестабильность" с сортировкой кучи. Что это значит?
Устойчивая сортировка поддерживает относительный порядок элементов, имеющих один и тот же ключ. Например, представьте, что ваш набор данных содержит записи с идентификатором сотрудника и именем. Начальный порядок:
1, Jim
2, George
3, Jim
4, Sally
5, George
Вы хотите сортировать по имени. Стабильная сортировка упорядочит элементы в следующем порядке:
2, George
5, George
1, Jim
3, Jim
4, Sally
Обратите внимание, что дубликаты записей для "Джорджа" находятся в том же относительном порядке, что и в исходном списке. То же самое с двумя записями "Джим".
Нестабильная сортировка может упорядочить элементы следующим образом:
5, George
2, George
1, Jim
3, Jim
4, Sally
Heapsort нестабилен, поскольку операции в куче могут изменить относительный порядок равных элементов. Не все реализации Quicksort стабильны. Это зависит от того, как вы реализуете разделение.
Несмотря на то, что Heapsort имеет худшую сложность O(n log(n)), это не говорит всей истории. В реальной реализации существуют постоянные факторы, которые теоретический анализ не учитывает. В случае с Heapsort vs. Quicksort выясняется, что существуют способы (например, медиана 5), чтобы сделать худшие случаи Quicksort очень редкими. Кроме того, сохранение кучи не является бесплатным.
Учитывая массив с нормальным распределением, Quicksort и Heapsort будут работать в O(n log(n)). Но Quicksort будет выполняться быстрее, потому что его постоянные факторы меньше постоянных факторов для Heapsort. Проще говоря, разбиение происходит быстрее, чем сохранение кучи.
Конфигурация кучи имеет худшую сложность O(n log(n)). Тем не менее эмпирические исследования показывают, что обычно Быстрый Сортировка (и другие алгоритмы сортировки) значительно быстрее, чем куча сортировки, хотя его наихудшая сложность O(n²): http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html
Кроме того, из статьи быстрого сортировки в Википедии:
Самым прямым конкурентом quicksort является heapsort. Время работы с наихудшим случаем Heapsort всегда равно O (n log n). Но предполагается, что heapsort будет в среднем несколько медленнее, чем стандартная быстрая сортировка. Это все еще обсуждается и в исследованиях, причем некоторые публикации указывают на обратное. [13] [14] Introsort - это вариант quicksort, который переключается на heapsort, когда обнаружен плохой случай, чтобы избежать худшего времени работы quicksort. Если заранее известно, что понадобится использовать heapsort, использование его напрямую будет быстрее, чем ждать, пока introsort не переключится на него.
Однако быстрый вид никогда не должен использоваться в приложениях, требующих гарантии времени отклика!
Источник на Stackoverflow: Quicksort vs heapsort
Нет серебряной пули...
Просто упомянуть еще один аргумент, который я еще не видел здесь:
Если ваш набор данных действительно огромен и не вписывается в память, то слияние сортировки работает как шарм. Он часто используется в кластерах, где набор данных может охватывать сотни машин.
Стабильные алгоритмы сортировки поддерживают относительный порядок записей с равными ключами
Некоторые приложения, такие как наличие такой стабильности, в большинстве случаев это не волнует, например, Google - ваш друг.
Как вы утверждаете, что "люди используют механизмы сортировки, такие как сортировка Merge или Quick sort", я бы поставил на то, что большинство людей используют все, что встроено в их язык, и не так много думают об алгоритме сортировки. Те, кто их собственный, вероятно, не слышали о сортировке кучи (последний - личный опыт).
Последняя и самая большая причина заключается в том, что не всем захочется сортировать кучу. Некоторым людям нужен отсортированный список. Если средний босс программиста Джо говорит "сортировать этот список", а Джо говорит: "Вот эта структура данных кучи, о которой вы никогда не слышали, босс!", Следующий обзор производительности Joe не будет таким большим.
Когда я работал в течение короткого времени на компьютерах Tandem Non-Stop в середине 80-х годов, я заметил, что системная процедура сортировки в ядре - это HeapSort, именно потому, что она обеспечила гарантированную производительность NlogN. Я не знаю никого, у кого есть какие-то причины для его использования, поэтому я не знаю, как это работает на практике. Мне нравится heapsort, но, как и недостатки, отмеченные выше, я слышал, что это говорит о том, что он плохо использует современные воспоминания, потому что он делает доступ к памяти повсюду, в то время как сортировка быстрой сортировки и даже небольшого радиуса заканчивается смешением относительно небольшого числа потоков последовательного чтения и записи - поэтому кеши более эффективны.