Quicksort по сравнению с пирамидальной сортировкой
И quicksort и пирамидальная сортировка делают оперативную сортировку. Который лучше? Каковы приложения и случаи, в которых любой предпочтен?
3 ответа
Эта статья содержит некоторый анализ.
Также из Википедии:
Самый прямой конкурент быстрой сортировки - это heapsort. Heapsort обычно несколько медленнее, чем quicksort, но в худшем случае время выполнения всегда равно Θ (nlogn). Быстрая сортировка обычно быстрее, хотя остается шанс на худой случай производительности , за исключением варианта внутренней сортировки, который переключается на heapsort, когда плохой случай {{ 1}} обнаружен. Если заранее известно, что heapsort будет необходим, использование его напрямую будет быстрее, чем ждать, пока интросорт переключится на него.
Heapsort строит кучу, а затем многократно извлекает максимальный элемент. Его наихудшим вариантом является O(n log n).
Но если вы увидите худший случай quick sort, который является O(n2), вы бы поняли, что быстрая сортировка будет не очень хорошим выбором для больших данных.
Таким образом, сортировка является интересной вещью; Я считаю, что причина, по которой так много алгоритмов сортировки живут сегодня, заключается в том, что все они «лучшие» в своих лучших местах. Например, пузырьковая сортировка может выполнять быструю сортировку, если данные отсортированы. Или, если мы знаем что-то о предметах, которые должны быть отсортированы, то, вероятно, мы можем сделать лучше.
Это может не ответить на ваш вопрос напрямую, подумал, что я добавлю свои два цента.
Heapsort имеет преимущество в наихудшем рабочем случае O (n * log (n)) , поэтому в случаях, когда быстрая сортировка, вероятно, будет работать плохо (в основном, сортировка наборов данных), heapsort очень предпочтительнее.