Каково различие между quicksort и настроенным quicksort?
Каково принципиальное различие между quicksort и настроенным quicksort? Что улучшение дано quicksort? Как Java решает использовать это вместо сортировки слиянием?
3 ответа
"Настроенная" быстрая сортировка просто означает, что к базовому алгоритму были применены некоторые улучшения. . Обычно улучшения заключаются в том, чтобы попытаться избежать наихудшей временной сложности. Некоторыми примерами улучшений могут быть выбор точки поворота (или нескольких точек поворота), чтобы в разделе никогда не было только одного ключа, или выполнение рекурсивного вызова только тогда, когда раздел превышает определенный минимальный размер.
Похоже, что Java использует сортировку слиянием только при сортировке объектов ( документ Arrays сообщает вам, какой алгоритм сортировки используется для какой сигнатуры метода сортировки), поэтому я не думаю, что он когда-либо действительно «решает» самостоятельно, но решение было принято заранее. (Кроме того, разработчики могут использовать другой вид, если он стабилен.)
В Java Arrays.sort (Object []) использует сортировку слиянием, но все другие перегруженные функции сортировки используют сортировку вставкой
, если длина меньше 7, а если длина массива больше 7, используется
настроенная быстрая сортировка.
Как сказал Билл Ящер, настроенная зыбкая сортировка по-прежнему имеет ту же сложность, что и базовая зыбкая сортировка - O(N log N) средняя сложность - но настроенная зыбкая сортировка использует некоторые различные средства, чтобы попытаться избежать O(N^2) наихудшей сложности, а также использует некоторые оптимизации, чтобы уменьшить константу, которая идет перед N log N для среднего времени работы.
Временная сложность наихудшего случая
Временная сложность наихудшего случая имеет место для quicksort, когда одна сторона раздела на каждом шаге всегда имеет нулевые элементы. Временная сложность, близкая к наихудшей, возникает, когда отношение элементов в одном разделе к другому очень далеко от 1:1 (например, 10000:1). Общие причины этой наихудшей сложности включают, но не ограничиваются:
Алгоритм quicksort, который всегда выбирает элемент с тем же относительным индексом подмассива в качестве стержня. Например, если массив уже отсортирован, сложность алгоритма quicksort, который всегда выбирает в качестве стержня крайний левый или крайний правый элемент подмассива, будет O(N^2). Алгоритм quicksort, который всегда выбирает средний элемент, дает O(N^2) для массива органных труб ([1,2,3,4,5,4,3,2,1] является примером этого).
Алгоритм quicksort, который не обрабатывает повторяющиеся/дублирующиеся элементы в массиве, может быть O(N^2). Очевидный пример - сортировка массива, который содержит все одинаковые элементы. В явном виде, если квиксорт сортирует массив на разделы типа [ < p | >= p ], то левый раздел всегда будет содержать нулевые элементы.
Как устранить эти проблемы? Первая проблема обычно решается случайным выбором стержня. Использование медианы нескольких элементов в качестве стержня также может помочь, но вероятность того, что сортировка будет O(N^2), выше, чем при использовании случайного стержня. Конечно, медиана нескольких случайно выбранных элементов тоже может быть разумным выбором. Медиана из трех случайно выбранных элементов в качестве стержня - обычный выбор здесь.
Второй случай, повторяющиеся элементы, обычно решается с помощью чего-то вроде разбиения Бентли-МакИлроя (ссылка на pdf) или решения проблемы голландского национального флага. Однако чаще всего используется разбиение Бентли-МакИлроя, поскольку оно обычно быстрее. Я придумал метод, который быстрее его, но это не суть важно для данного сообщения.
Оптимизации
Вот некоторые общие оптимизации, не относящиеся к перечисленным выше методам и помогающие в худших случаях:
Использование сходящейся сортировки по указателям в отличие от базовой сортировки. Дайте мне знать, если вы хотите получить более подробную информацию об этом.
Вставная сортировка подмассивов, когда они становятся меньше определенного размера. Сортировка вставками асимптотически O(N^2), но для достаточно малых N она выигрывает у quicksort.
Использование итеративной квиксортировки с явным стеком в отличие от рекурсивной квиксортировки.
Разворачивание частей циклов для уменьшения числа сравнений.
Копирование стержня в регистр и использование этого места в массиве для уменьшения временных затрат на замену элементов.
Другие заметки
Java использует mergesort при сортировке объектов, потому что это стабильная сортировка (порядок элементов, имеющих одинаковый ключ, сохраняется). Quicksort может быть стабильной или нестабильной, но стабильная версия медленнее, чем нестабильная.