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