Я никогда раньше не видел двойного поворота.
Если это версия обновления быстрой сортировки?
И в чем разница между быстрым сортированием и быстрой сортировкой двойного шага?
Какая разница в быстром сортировке и быстрой сортировке двойного шарнира?
Ответ 1
Я нахожу это в документе Java.
Алгоритм сортировки - это двойная поворотная быстрая сортировка Владимира Ярославского, Джона Бентли и Джошуа Блоха. Этот алгоритм обеспечивает производительность O (n log (n)) для многих наборов данных, которые приводят к ухудшению квадратичной производительности других быстрых сортировок, и, как правило, быстрее, чем традиционные реализации (с одним поворотом) быстрой сортировки.
Затем я нахожу это в результатах поиска Google. Вот алгоритм быстрой сортировки:
- Выберите элемент, называемый сводной, из массива.
- Переупорядочьте массив таким образом, чтобы все элементы, меньшие, чем сводка, располагались перед сводкой, а все элементы, большие, чем сводка, следовали за ней (равные значения могут идти в любом случае). После этого разбиения элемент поворота находится в своем окончательном положении.
- Рекурсивно сортировать вложенный массив меньших элементов и вложенный массив больших элементов.
Для сравнения: быстрая сортировка с двумя точками поворота:
()
- Для небольших массивов (длина <17) используйте алгоритм сортировки вставками.
- Выберите два поворотных элемента P1 и P2. Например, мы можем получить первый элемент a [left] как P1 и последний элемент a [right] как P2.
- P1 должен быть меньше P2, иначе они меняются местами. Итак, есть следующие части:
- часть я с индексами слева + 1 до L – 1 с элементами, которые меньше, чем P1,
- часть II с индексами от L до K – 1 с элементами, которые больше или равны P1 и меньше или равны P2,
- часть III с индексами от G + 1 вправо – 1 с элементами больше, чем P2,
- часть IV содержит остальные элементы, которые нужно исследовать с индексами от K до G.
- Следующий элемент a [K] из части IV сравнивается с двумя осями P1 и P2 и помещается в соответствующую часть I, II или III.
- Указатели L, K и G меняются в соответствующих направлениях.
- Шаги 4 - 5 повторяются, пока K ≤ G.
- Поворотный элемент P1 заменен последним элементом из части I, поворотный элемент P2 заменен первым элементом из части III.
- Шаги 1 - 7 повторяются рекурсивно для каждой части I, части II и части III.
Ответ 2
Для тех, кто заинтересован, посмотрите, как они реализовали этот алгоритм в Java:
Как указано в источнике:
"Сортирует заданный диапазон массива с использованием заданного массива массива рабочего пространства, если возможно, для слияния
Алгоритм обеспечивает производительность O (n log (n)) во многих наборах данных, которые приводят к снижению производительности в быстродействующих сегментах до квадратичной производительности и обычно быстрее, чем традиционные (однопоточные) реализации Quicksort.
Ответ 3
Я просто хочу добавить, что с точки зрения алгоритма (т.е. Стоимость учитывает только количество сравнений и перестановок), 2-pivot quicksort и 3-pivot quicksort не лучше, чем классическая quicksort (которая использует 1 pivot), если нет хуже. Однако на практике они работают быстрее, поскольку используют преимущества современной компьютерной архитектуры. В частности, их количество кешей меньше. Поэтому, если мы удалим все кэши и останемся только процессор и основная память, в моем понимании, 2/3-пивотная быстрая сортировка хуже, чем классическая быстрая сортировка.
Ссылки: 3-pivot Quicksort: https://epubs.siam.org/doi/pdf/10.1137/1.9781611973198.6 Анализ того, почему они работают лучше классической Quicksort: https://arxiv.org/pdf/1412.0193v1.pdf Полная и не слишком подробная информация: https://algs4.cs.princeton.edu/lectures/23Quicksort.pdf