Можно ли выполнить быструю сортировку с использованием очереди?
Я нашел эту статью только https://www.quora.com/Can-we-use-a-queue-in-quicksort-in-C.
Правильно ли это?
Если да, то почему учебник всегда реализует быструю сортировку по стеку или рекурсивному методу?
Потому что информация об этом вопросе встречается редко, поэтому я прошу здесь.Быстрая сортировка по очереди?
почему учебник всегда осуществлять быструю сортировку по стеку или рекурсивный метод только
Поскольку суть сортировки в том, что он находится в месте, и сортировка достигается за счет повторных разделов одного и того же массива который сортируется.
Перегородки выполняются сверху вниз, от более крупных частей массива до меньших и меньших.
Если мы используем стек для управления с работой еще, чтобы быть сделано, то размером этого пакет будет размером массива логарифмической (если раздел оказывается на стеке тем больше, всегда). Это эквивалентно обходу глубины.
Но если бы мы использовать очередь для этого, было бы эквивалентно в ширину обхода, и размер очереди будет линейный (который экспоненциально хуже, чем логарифмическая).
Если меньший раздел всегда помещается в стек, то размер стека гарантированно равен O (log n). (Это предполагает явный стек и цикл, в котором после разбиения на разделы один раздел складывается, а другой обрабатывается.) – rici
@rici еще лучше! спасибо за подсказку. :) –
Извините за мысль, я исправил комментарий слишком поздно. Утверждение легко доказать: каждый сложный раздел меньше половины размера предыдущего, поэтому общая высота является самой логарифмической. На практике это может быть константой, поскольку журнал количества сортируемых элементов ограничен физическими ограничениями. 60 было бы более чем достаточно. – rici
bad cache performance
С стека, мы имеем достаточно временной локальности, в то время как с очередью она теряется полностью. Мы в основном пытаемся отсортировать массив по ширине первого способа поиска в методе очереди.
EDIT (из ответа Will Ness): И более крупные массивы (> ОЗУ), метод очереди даже не работает, поскольку для сортировки массива размером n требуется пространство O (n). Хотя для метода на основе стека требуется только лог-пространство. Вся теоретическая временная сложность обоих из них одинакова.
Я не рассматривал статью. Вопросы о СО должны быть более или менее самодостаточными. Вы можете суммировать его содержимое и добавить его к вопросу. –