Я провел несколько тестов и обнаружил, что quicksort на самом деле работает медленнее, чем больше отсортированный список, а довольно противоречивый! Я прочитал алгоритм быстрой сортировки по википедии, но я не совсем понимаю, почему это занимает больше времени, чем больше отсортировано. Любая помощь будет оценена!Quicksort занимает больше времени в отсортированных списках
Нерандомизированная быстрая сортировка обычно выбирает первый элемент как элемент поворота; когда список уже отсортирован, это приведет к тому, что список будет разделен на пустой левый список и правый список, содержащий n-1 элементов. Же поведение будет происходить в каждом рекурсивном вызове, а общее время выполнения будет п + п-1 + п-2 + ... = O (N^2).
, если вы хотите гарантировать O (nlogn), используйте медианную медианную информацию для поворота выбор – Daniel
@ Daniel - если вы хотите гарантировать O (n log n), гораздо разумнее использовать слияние или хаппорт. Медиана медианов может дать вам вашу асимптотическую гарантию (я не проверял дважды), но она сложная, и постоянные факторы будут довольно бедными. – Steve314
@ Steve314, я знал, что есть накладные расходы, но, поскольку я никогда не использовал его в действительности, я не знал, сколько. Спасибо за подсказку :) – Daniel
Что вы имеете в виду, это хорошо известная проблема с QuickSort. Одним из способов решения проблемы является использование элемента, отличного от первого, в качестве элемента поворота.
Эта запись StackExchange имеет очень хорошие записи на QuickSort в целом: https://cs.stackexchange.com/questions/3/why-is-quicksort-better-than-other-sorting-algorithms-in-practice
Эта статья идет гораздо более глубокий и занимает в этом вопросе для уже отсортированного списка и способов реализации QuickSort, что работа такого рода аномалии. http://www.csie.ntu.edu.tw/~b93076/p847-sedgewick.pdf
Сообщите свой код, если вы хотите получить помощь. Я также думаю, что этот вопрос больше подходит для [Программистов] (http://programmers.stackexchange.com/). – Renan
в основном в отсортированном списке, quicksort будет стремиться в начале перетасовать список. – njzk2
Эта конкретная часть статьи в Википедии объясняет расчёт для сценария наихудшего случая http://en.wikipedia.org/wiki/Quicksort#Average-case_analysis_using_recurrences – njzk2