Временная сложность
В среднем: O (NLGN)
В худшем случае: O (n*n), происходит, когда данные уже находятся в состоянии сортировки.
1. Выберите значение a [i] из данных в качестве ссылки
2. Взяв [i] в качестве ссылки, разделите данные на 2 части: P1 и P2. Все данные в p1≤a [i], все данные в p2> a [i], и данные становится {{p1} {a [i]} {p2}}
3. Повторите вышеуказанные шаги с P1 и P2, пока в каждой части не останется только 1 данные.
4. Данные отсортированы в порядке возрастания
Основной пример:
Необработанные данные:
{3, 9, 8, 5, 2, 1, 6} Шаг 1: Выберите первые данные: 3
Шаг 2: Разделите данные на 2 части, левая сторона ≤3, а правая сторона больше, чем> 3:
{2,1} {3} {9,8,5,6} Шаг 3: Повторите вышеуказанные шаги для каждой части, пока в каждой части останется только 1 данные:
{2,1} => {1} {2} {9, 8, 5, 6} => {8, 5, 6} {9} => {5, 6} {8} {9} => {5} {6} {8} {9} => {5} {6} {8} {9} Шаг 4: Данные отсортированы в порядке возрастания:
{1} {2} {3} {5} {6} {8} {9}Данные в программе обычно хранятся в массиве. Принимая массив типа Int в качестве примера, вы можете написать вышеуказанные шаги в прототип функции QuickSort:
QuickSort (int begin, int end) {// begin-это значение индекса первых данных массива, End-это значение индекса последних данных массива +1 // Если есть только 1 данные или 0 данных, программа возвращает, если (begin == end || begin == (end-1)) возврат; int p = in [begin]; // p - выбранные справочные данные, выберите первые данные int a = begin +1; // a как значение индекса 2-часовой линии разделения данных int b = a; // b является значением индекса данных, которые должны сравниваться для (; b <end; b ++) {// Сравните данные в массиве с эталонными данными в последовательности, если (в [b] <p) {// если данные <ссылки, переместите его влево, если (a == b) {AT ++; Продолжить;} // Если данные уже слева, он не будет перемещать int temp = in [a]; // Переместить данные влево в [a] = in [b]; в [b] = temp; a ++; // переместить разделительную линию вправо}} в [begin] = в [a-1]; // whike эталонное значение в середину 2 наборов данных в [a-1] = p; if (a-1> begin) {// Если есть данные слева, повторите вышеуказанные шаги QuickSort (начало, a); } if (end-1> a) {// Если есть данные справа, повторите вышеуказанные шаги QuickSort (a, end); } возвращаться; // Если нет данных} Оптимизация алгоритма
Приведенный выше алгоритм быстрого сортировки можно сказать, что является самым основным быстрым сортировкой, поскольку он не учитывает никаких входных данных. Тем не менее, легко найти недостатки этого алгоритма: это когда наши входные данные в основном упорядочены или даже полностью упорядочены, алгоритм дегенератизируется в сортировку пузырьков, больше не O (nn), но O (n^2).
Основная причина заключается в том, что в нашей реализации кода мы начинаем только с первого массива за раз. Если мы используем «Трехедний», то есть медианные значения ARR [low], ARR [HIGH], ARR [(LOW+HIGH)/2] в качестве записи PIVOT, производительность быстрой сортировки в худшем сценарии может быть значительно улучшена. Тем не менее, мы все еще не можем улучшить его производительность до O (n) в случае с упорядоченным массивом. Есть также способы улучшить время быстрой сортировки в наихудшем сценарии в различной степени.
Кроме того, быстрая сортировка требует рекурсивного стека, который обычно не очень глубокий и находится на уровне логарифма (n). Однако, если длина двух массивов, разделенных за раз, сильно несбалансирована, в худшем случае глубина стека увеличится до O (n). В настоящее время пространственная сложность, вызванная пространством стека, нельзя игнорировать. Если добавлены накладные расходы дополнительных переменных, он может даже достичь ужасной сложности пространства O (n^2) здесь. Следовательно, худшая пространственная сложность быстрой сортировки не является фиксированным значением и может даже не быть на одном уровне.
Чтобы решить эту проблему, мы можем сравнить длины концов после каждого деления и сначала сортировать короткие последовательности (цель состоит в том, чтобы сначала закончить эти стеки, чтобы освободить пространство), что может уменьшить максимальную глубину назад до уровня O (n).
Вот три идеи оптимизации для быстрой сортировки:
Для небольших массивов можно использовать сортировку вставки, чтобы избежать рекурсивных вызовов. Например, когда (hi <= lo + m) вы можете перейти на вставку сортировки.
Используйте медиана subarray, чтобы нарезать массив. Это приводит к лучшему нарезку, но за счет расчета медианы.
Если массив содержит большое количество повторяющихся элементов, можно использовать трехстороннее нарезку. Разделите массив на три части, соответствующие массивам элементам меньше, чем, равно и больше, чем нарезание элементов соответственно. Реализация кода выглядит следующим образом:
private static void sort1 (int [] a, int lo, int hi) {if (hi <= lo) return; int lt = lo, i = lo + 1, gt = hi; int v = a [lo]; while (i <= gt) {if (a [i] <v) {swap (a, lt ++, i ++); } else if (a [i]> v) {swap (a, i, gt--); } else {i ++; } sort (a, lo, lt - 1); сортировка (a, gt + 1, hi); }}