Двухпутевая быстрая сортировка

Алгоритм двусторонней быстрой сортировки — улучшенная версия рандомизированной быстрой сортировки. В процессе разделения используются два значения индекса (i, j) для обхода массива, при этом размещая<vэлементы слева от позиции, на которую указывает индекс i, и размещая>vэлементы справа от позиции, на которую указывает индекс j,vОбозначает опорное значение.

Применимость

Временная и пространственная сложность такие же, как у рандомизированной быстрой сортировки. Для массивов с большим количеством повторяющихся элементов использование рандомизированной быстрой сортировки из предыдущего раздела очень неэффективно, потому что длины подмассивов после разделения для данных больше или меньше опорного элемента становятся крайне несбалансированными, и она может даже выродиться в алгоритм сO(n*2)временной сложностью. В этой ситуации можно использовать алгоритм двусторонней быстрой сортировки.

Схема процесса

Используйте два значения индекса (i, j) для обхода нашей последовательности, размещая<=vэлементы слева от позиции, на которую указывает индекс i, и размещая>=vэлементы справа от позиции, на которую указывает индекс j, балансируя левый и правый подмассивы.

Пример кода на Java

Загрузка пакета исходного кода:Скачать

Код файла QuickSort2Ways.java:

package example;

/**
* Двусторонняя быстрая сортировка
 */
public class QuickSort2Ways {

    // Основной код --- начало
    private static int partition(Comparable[] arr, int l, int r){
        // Случайным образом выбрать значение в качестве опорного элемента в диапазоне arr[l...r]
        swap( arr, l , (int)(Math.random()*(r-l+1))+l );
        Comparable v = arr[l];
        // arr[l+1...i) <= v; arr(j...r] >= v
        int i = l+1, j = r;
        while( true ){
            while( i <= r && arr[i].compareTo(v) < 0 )
                i ++;
            while( j >= l+1 && arr[j].compareTo(v) > 0 )
                j --;
            if( i > j )
                break;
            swap( arr, i, j );
            i ++;
            j --;
        }
        swap(arr, l, j);
        return j;
    }
    // Основной код --- конец

    // Рекурсивно применяйте быструю сортировку для сортировки диапазона arr[l...r]
    private static void sort(Comparable[] arr, int l, int r){
        if (l >= r) {
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p-1 );
        sort(arr, p+1, r);
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;
        sort(arr, 0, n-1);
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // Тестирование QuickSort
    public static void main(String[] args) {

        // Двухсторонняя быстрая сортировка — это также алгоритм сложности O(nlogn)
        // Может легко обрабатывать данные порядка 1 миллиона за 1 секунду

        // Быстрая сортировка также является алгоритмом со сложностью O(n log n)
        // Может легко обрабатывать данные порядка 1 миллиона за 1 секунду
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        SortTestHelper.printArray(arr);

    }
}

Подробное объяснение принципа алгоритма

Ядро двухсторонней быстрой сортировки заключается в еёметоде разбиения с двумя указателямиВ отличие от односторонней быстрой сортировки (которая сканирует только с одного конца), она использует два указателя, которые сканируют от начала и конца сортируемого подмассива к середине, гарантируя, что равные элементы не все сдвигаются в одну сторону.

Суть: процесс двухстороннего разбиения

Предположим, мы хотим отсортировать массивarrсредний индекс отleftвrightчасть.

Выберите опорное значение: изarr[left...right]Случайным образом выберите из него элемент в качестве опорного значенияpivotРандомизация используется, чтобы избежать худшего случая на отсортированных массивах.

Инициализируйте указатели：

  • i = left + 1Указатель, сканирующий слева направо, ищет первыйбольший или равный pivotelements.
  • j = rightУказатель, сканирующий справа налево, ищет первыйменьший или равный pivotelements.

Цикл сканирования и обмена：

  • whileЦикл, условием которого являетсяi <= j。
  • внутреннийwhileloop: letiПродолжайте двигаться вправо, покаarr[i] >= pivot。
  • внутреннийwhileloop: letjПродолжайте двигаться влево, покаarr[j] <= pivot。
  • В этот момент,arr[i]является «большим» элементом, который не должен находиться в левой половине,arr[j]является «маленьким» элементом, который не должен находиться в правой половине.
  • Если в этот моментi <= j, то поменяйте местамиarr[i]иarr[j], затемi++, j--затем продолжайте внешний цикл.

Поместите значение опорного элемента и верните точку разделения：

  • После завершения цикла,iиjуже пересеклись (j < i). В этот моментarr[left](т. е. опорный элемент) нужно поместить в правильную позицию.
  • будетarr[left]иarr[j]swap. Потому чтоjПозиция, на которой он в итоге останавливается, а элемент, на который он указывает, — этопоследний элемент, меньший или равный опорному значениюэлементы.
  • returnjкак новую точку разбиения. На этом этапе,arr[left...j-1] <= pivot，arr[j+1...right] >= pivot, иarr[j] == pivot。

рекурсивно сортировать

получаем точку разбиенияpПосле этого для левого подмассиваarr[left...p-1]и правого подмассиваarr[p+1...right]Повторяйте описанный процесс рекурсивно, пока длина подмассива не станет равной 1.

Реализация кода

Давайте конкретно разберём двустороннюю быструю сортировку на примере полной реализации на Java.

1. Основная функция сортировки

Пример

public class TwoWayQuickSort {

    // Публичный интерфейс сортировки
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return; // Обработать граничное условие: массив пуст или содержит только один элемент, сортировка не требуется
        }
        quickSort(arr, 0, arr.length - 1); // Вызов рекурсивной функции быстрой сортировки
    }

    // Рекурсивная функция быстрой сортировки
    private static void quickSort(int[] arr, int left, int right) {
        // Условие завершения рекурсии: когда left >= right, подмассив уже отсортирован или пуст
        if (left >= right) {
            return;
        }
       
        // Ключевой шаг: выполнить двустороннее разбиение и вернуть индекс разбиения
        int p = partition(arr, left, right);
       
        // Рекурсивно сортируем левую половину (left, p-1)
        quickSort(arr, left, p - 1);
        // Рекурсивно сортируем правую половину (p+1, right)
        quickSort(arr, p + 1, right);
    }
}

2. Ядро: функция двустороннего разбиения

Это ядро алгоритма. Пожалуйста, внимательно разберитесь в нём вместе с приведённой выше блок-схемой и комментариями.

Пример

    // Функция двустороннего разбиения
    private static int partition(int[] arr, int left, int right) {
        // 1. Случайно выбираем опорный элемент и переставляем его в левую позицию, избегая наихудшего случая на отсортированных массивах
        int randomIndex = left + (int)(Math.random() * (right - left + 1));
        swap(arr, left, randomIndex);
        int pivot = arr[left]; // Значение опорного элемента
       
        // 2. Инициализация двух указателей
        // i: сканировать слева направо в поиске элементов >= pivot
        // j: сканировать справа налево в поиске элементов <= pivot
        int i = left + 1;
        int j = right;
       
        // 3. Основной цикл: пока i и j не пересеклись
        while (i <= j) {
            // 3.1 Переместить левый указатель i: найти первый элемент >= pivot
            // Примечание: граница i <= right для предотвращения выхода за пределы массива
            while (i <= right && arr[i] < pivot) {
                i++;
            }
            // 3.2 Переместить правый указатель j: найти первый элемент <= pivot
            // Примечание: граница j >= left+1, потому что позиция left — это сам pivot
            while (j >= left + 1 && arr[j] > pivot) {
                j--;
            }
           
            // 3.3 Проверка состояния указателей
            // Если i > j, сканирование завершено, левая и правая части готовы, менять местами не нужно
            if (i > j) {
                break;
            }
           
            // 3.4 Поменять местами arr[i] и arr[j]
            // Теперь arr[i] >= pivot, arr[j] <= pivot, поменяйте их местами, чтобы элементы с обеих сторон оказались на своих местах
            swap(arr, i, j);
            // После обмена переместите указатели, чтобы продолжить сканирование
            i++;
            j--;
        }
       
        // 4. Поместите pivot в его окончательную правильную позицию j
        // После завершения цикла j указывает на последний элемент <= pivot
        swap(arr, left, j);
       
        // 5. Вернуть индекс j точки разделения
        return j;
    }
   
    // Вспомогательная функция: поменять местами позиции двух элементов в массиве
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

3. Тестирование и проверка

Давайте протестируем нашу реализацию на массиве, содержащем дублирующиеся элементы.

Пример

public class Main {
    public static void main(String[] args) {
        // Тестовый случай 1: массив, содержащий много дублирующихся элементов
        int[] arr1 = {4, 2, 2, 8, 3, 3, 1, 5, 3, 2};
        System.out.println("Перед сортировкой: " + Arrays.toString(arr1));
        TwoWayQuickSort.sort(arr1);
        System.out.println("После сортировки: " + Arrays.toString(arr1));
       
        // Тестовый случай 2: большой массив, сгенерированный случайным образом
        int[] arr2 = new int[20];
        Random rand = new Random();
        for (int i = 0; i < arr2.length; i++) {
            arr2[i] = rand.nextInt(50); // Генерируем случайные числа от 0 до 49, возможны дубликаты
        }
        System.out.println("\n"Перед сортировкой массива случайных чисел: " + Arrays.toString(arr2));
        TwoWayQuickSort.sort(arr2);
        System.out.println("После сортировки массива случайных чисел: " + Arrays.toString(arr2));
       
        // Проверяем, правильно ли отсортирован результат
        for (int i = 1; i < arr2.length; i++) {
            if (arr2[i] < arr2[i-1]) {
                System.out.println("Ошибка сортировки!");
                return;
            }
        }
        System.out.println("Проверка результата сортировки пройдена!");
    }
}

Пример вывода тестовых данных：

排序前: [4, 2, 2, 8, 3, 3, 1, 5, 3, 2]
排序后: [1, 2, 2, 2, 3, 3, 3, 4, 5, 8]

随机数组排序前: [17, 33, 12, 48, 8, 2, 41, ...]
随机数组排序后: [2, 8, 12, 17, 33, 33, 41, 48, ...]
排序结果验证通过！

Анализ и сравнение алгоритмов

Временная сложность

  • Средний случай:$O(n \log n)$. Двусторонняя быстрая сортировка поддерживает дерево рекурсии относительно сбалансированным, равномерно распределяя дублирующиеся элементы.
  • Худший случай:$O(n^2)$. Хотя рандомизированный выбор опорного элемента значительно снижает вероятность, худший случай всё ещё может возникнуть, когда каждое разбиение крайне несбалансировано (например, когда опорный элемент всегда является текущим минимальным или максимальным значением).
  • Лучший случай:$O(n \log n)$. Каждое разбиение делит массив равномерно.

Пространственная сложность

  • В основном это пространство, занимаемое стеком рекурсивных вызовов.
  • Средняя глубина — $O(\log n)$, а глубина в худшем случае — $O(n)$.
  • Следовательно,Средняя пространственная сложность — $O(\log n)$, а в худшем случае — $O(n)$.。

Стабильность

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

Сравнение односторонней, двусторонней и трёхсторонней быстрой сортировки

Особенности Односторонняя быстрая сортировка (Ломуто) Двухпутевая быстрая сортировка Быстрая сортировка с трёхсторонним разбиением
Метод разбиения Один указатель сканирует слева направо Два указателя сканируют с обоих концов к середине Три указателя, разделяющие массив на<pivot, =pivot, >pivotТри части
Обработка повторяющихся элементов Плохо, может привести к несбалансированному разбиению Хорошо, может равномерно распределять повторяющиеся элементы Оптимально, может обрабатывать все элементы, равные опорному элементу, за один раз
Сложность кода Простая Средняя Немного сложный
Применимые сценарии Обучение, нет/мало дублирующихся элементов Универсальный, особенно подходит для сценариев, где могут присутствовать дублирующиеся элементы Сценарии с большим количеством дублирующихся элементов

Больше примеров кода

Другие расширения