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