Быстрая сортировка и ее оптимизация

алгоритм Алгоритм сортировки

Введение

Как следует из названия,быстрая сортировкаэто алгоритм быстрой сортировки на практике, в C++ или дляОсновные типы Javaособенно полезно при сортировке. этоСреднее время выполнения — O(NlogN), но производительность в наихудшем случае — O(N2).Сначала я расскажу о процессе быстрой сортировки, а затем расскажу, как его оптимизировать.

Во-вторых, быстрая сортировка (quicksort)

  • Алгоритмическое мышление:

Разделите массив на две части и вызовите его рекурсивно.Процесс быстрой сортировки для сортировки массива S

  1. Если количество элементов в S равно 0 или 1, вернитесь напрямую;
  2. Возьмите любой элемент v в S и назовите его стержнем; [Стратегия выбора поворотного элемента очень важна, о чем будет подробно рассказано ниже.】
  3. Разделите S-{v} (остальные элементы в S, кроме опорного элемента) на два непересекающихся множества S1и С2, С1Все элементы в наборе меньше или равны опорному элементу v, S2Все элементы больше или равны опорному элементу;
  4. вернуть быструю сортировку (S1), опорный элемент v, быстрая сортировка (S1).
  • Стратегия выбора опорного элемента
  1. Возьмите первое или последнее:простой, ноглупый(Ах, 9 драконов, картинка выше???). Когда входная последовательность находится в порядке возрастания или убывания, это приведет к S1Набор пуст, все элементы, кроме опорного, находятся в S2коллекция, эта практика,Наихудшая временная сложность O(N2).
  2. случайный выбор:Этобезопаснееспособ сделать. Если нет ошибки в генераторе случайных чисел, и вероятность непрерывного создания плохих сегментаций относительно низка. Однако генерация случайных чисел стоит дорого, что увеличивает время работы.
  3. трехзначный медианный метод: последовательностьМедиана (медиана) — лучший выбор для опорного элемента (поскольку последовательность можно поровну разделить на две подпоследовательности,Сортировка слияниемСкажите, на этот раз O(NlogN); но вычисление медианы набора массивов занимает много времени, что снижает эффективность быстрой сортировки. ноЕго можно заменить вычислением медианы первого, среднего и последнего элементов массива.Например, последовательность: [8, 1, 4, 9, 6, 3, 5, 2, 7, 0]. Первый элемент равен 8, средний (левый+правый)/2 (округлить вниз) элемент равен 6, а последний элемент равен 0. Таким образом, медиана равна 6, т. е. опорный элемент равен 6. По-видимому, использование метода разделения на треть устраняет плохой случай предварительно отсортированного ввода и фактически уменьшает количество сравнений на 14%.
  • Быстрый процесс сортировки

  1. Поменяйте местами элемент сводки с последним элементом массива, чтобы элемент сводки оставил разделяемый сегмент данных;

  2. Инициализировать два индекса слева и справа, указывая на первый и предпоследний элементы массива соответственно;

  3. Если элемент, на который указывает левый индекс, меньше, чем опорный элемент, то левый++, иначе левый останавливается. Элемент, на который указывает правый индекс, больше, чем опорный элемент, правый--, в противном случае правый останавливается.

  4. Если левый

    Предполагается, что все элементы различны (т. е. не равны).Далее пойдет речь о том, как бороться с повторяющимися элементами.

    Следующее, что нужно сделать, это переместить элементы, меньшие, чем опорный элемент, влево от массива, а элементы, превышающие опорный элемент, — вправо от массива.

    Когда левый находится слева от правого, мы перемещаемся слева направо по тем элементам, которые меньше, чем опорный элемент, и двигаемся справа налево по тем элементам, которые больше, чем опорный элемент. Когда левый и правый останавливаются, левый указывает на элемент, больший, чем опорный элемент, а правый указывает на элемент, меньший, чем опорный элемент.Если левый

    Мы меняем местами элементы, на которые указывает левый и правый,Повторяйте этот процесс, пока слева> справа.

    На данный момент мы видим, что элементы слева меньше, чем опорный элемент, а элементы справа больше, чем опорный элемент. Мы продолжаем рекурсировать левую и правую последовательности, и, наконец, сортировка может быть завершена.

    Выше мы предполагали, что элементы отличаются друг от друга, а теперь обсудим обработку повторяющихся элементов.

  • Обработка повторяющихся элементов: Проще говоря, когда встречается элемент, равный поворотному элементу, нужно ли останавливать левую и правую индексацию?
  1. Если только один из них останавливается:Это включает в себя и то, и другое, если только левое или правое индексирование остановлено, это приведет к перемещению элементов, равных опорному элементу, в набор. Рассмотрим последовательностьВсе элементы являются повторяющимися элементами,будетХудший случай O(N2).
  2. Если ни одна из них не остановится:Это необходимо для предотвращения выхода левого и правого индекса за границы, а не для замены элементов. Но правильный процесс, как показано выше, заключается в том, что поворотный элемент необходимо поменять местами с элементом, на который указывает левый индекс. все еще считаюВсе элементы одинаковы, это приведет к тому, что последовательность будет полностью разделена влево, так что она по-прежнемуХудший случай O(N2).
  3. оба останавливаются:все еще считаювсе элементы равныВ этом случае кажется, что будет много «бессмысленных» обменов, но положительный эффект заключается в том, что левое и правое чередование происходит в средней позиции, в это время последовательность просто делится на две подпоследовательности, или принцип сортировки слиянием , этоО(NlogN).Наш анализ показывает, что только в этом случае можно избежать квадратичного уравнения.

В крупномасштабном вводе по-прежнему довольно много повторяющихся элементов. По-прежнему важно учитывать, что эти повторяющиеся элементы можно эффективно сортировать.

Быстрая сортировка действительно быстрая?Не обязательно, на самом деле.Для входных последовательностей небольших массивов (N Сортировка вставками;А в нашей оптимизации выше, когда для деления используется трехзначная медиана, результат, полученный рекурсивно, может состоять только из одного или двух элементов, и в это время будет ошибка. Итак, дальнейшая оптимизация заключается в замене небольших последовательностей сортировкой вставками, что сокращает время выполнения примерно на 15%.Хороший диапазон отсечки — 10.(На самом деле 5-20 дают почти такой же эффект).

заРазделение медианы по трем числам также может быть оптимизировано.: Предполагая, что входная последовательность представляет собой а, выберите а [слева], а [центр], а [право] и выберите значение поворота,И поместите минимальное и максимальное значения в [лево], [право] соответственно, и поместите значение поворота в [право-1], чтобы размещение также было правильным положением,и можетПредотвратить выход правого за границы при сравнении с правым;Таким образом, левая и правая начальные позиции — левая+1, правая-2.

В-третьих, оптимизируйте сводную реализацию Java быстрой сортировки: 

public class Quicksort {
    /**
     * 截止范围
     */
    private static final int CUTOFF = 10;

    public static void main(String[] args) {
        Integer[] a = {8, 1, 4, 9, 6, 3, 5, 2, 7, 0};
        System.out.println("快速排序前：" + Arrays.toString(a));
        quicksort(a);
        System.out.println("快速排序后：" + Arrays.toString(a));
    }

    public static <T extends Comparable<? super T>> void quicksort(T[] a) {
        quicksort(a, 0, a.length - 1);
    }

    private static <T extends Comparable<? super T>> void quicksort(T[] a, int left, int right) {
        if (left + CUTOFF <= right) {
            //三数中值分割法获取枢纽元
            T pivot = median3(a, left, right);

            // 开始分割序列
            int i = left, j = right - 1;
            for (; ; ) {
                while (a[++i].compareTo(pivot) < 0) {
                }
                while (a[--j].compareTo(pivot) > 0) {
                }
                if (i < j) {
                    swapReferences(a, i, j);
                } else {
                    break;
                }
            }
            //将枢纽元与位置i的元素交换位置
            swapReferences(a, i, right - 1);
            //排序小于枢纽元的序列
            quicksort(a, left, i - 1);
            //排序大于枢纽元的序列
            quicksort(a, i + 1, right);
        } else {
            //插入排序
            insertionSort(a, left, right);
        }
    }

    private static <T extends Comparable<? super T>> T median3(T[] a, int left, int right) {
        int center = (left + right) / 2;
        if (a[center].compareTo(a[left]) < 0) {

            swapReferences(a, left, center);
        }
        if (a[right].compareTo(a[left]) < 0) {
            swapReferences(a, left, right);
        }
        if (a[right].compareTo(a[center]) < 0) {
            swapReferences(a, center, right);
        }
        // 将枢纽元放置到right-1位置
        swapReferences(a, center, right - 1);
        return a[right - 1];
    }

    public static <T> void swapReferences(T[] a, int index1, int index2) {
        T tmp = a[index1];
        a[index1] = a[index2];
        a[index2] = tmp;
    }

    private static <T extends Comparable<? super T>> void insertionSort(T[] a, int left, int right) {
        for (int p = left + 1; p <= right; p++) {
            T tmp = a[p];
            int j;

            for (j = p; j > left && tmp.compareTo(a[j - 1]) < 0; j--) {
                a[j] = a[j - 1];
            }

            a[j] = tmp;
        }
    }

}
//输出结果
//快速排序前：[8, 1, 4, 9, 6, 3, 5, 2, 7, 0]
//快速排序后：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Четыре, быстрый анализ сортировки

  1. Худшая временная сложность:То есть элементы разбиты на одну подпоследовательность, а другая подпоследовательность пуста,Временная сложность O(N2).
  2. Лучшая временная сложность:То есть последовательность равномерно делится на две подпоследовательности, а временная сложность равнаO(NlogN), анализ аналогичен сортировке слиянием.
  3. Средняя временная сложность: O(NlogN).
  4. Пространственная сложность: O(logN)

V. Резюме

Эта статья оптимизирует быструю сортировку с трех аспектов: как лучше выбрать опорные элементы, проанализировать обработку повторяющихся элементов и заменить ее сортировкой вставками при рекурсивном разделении на небольшие массивы Система всесторонне описывает принцип, процесс и оптимизацию быстрой сортировки. Быстрая сортировка выполняется в среднем за время O(NlogN) и является алгоритмом сортировки, используемым базовыми типами в java. Вы можете взглянуть на метод Arrays.sort. Вот, я повернусьИдеальное решение проблемы topKТеперь вы можете использовать идею быстрой сортировки для достижения среднего решения O(N) для topK.

Если вы считаете, что это возможно, пожалуйста, дайте рекомендацию или небольшой лайк, чтобы поддержать это.

Категории