Быстрая сортировка на Java — пошаговая реализация с разбором

Быстрая сортировка (Quick Sort) — один из самых быстрых и популярных алгоритмов сортировки. Его придумал британский программист Тони Хоар в 1960 году. В отличие от сортировки пузырьком, быстрая сортировка использует принцип «разделяй и властвуй» (divide and conquer): задача разбивается на более простые подзадачи, каждая решается отдельно, а затем результаты объединяются.

Идея алгоритма:

  1. Выбираем из массива один элемент — он называется опорным (pivot). Чаще всего берут крайний правый элемент.

  2. Разделяем массив на две части: слева ставим все элементы, которые меньше опорного, справа — все, которые больше.

  3. Сам опорный элемент после такого разделения сразу занимает своё окончательное место в отсортированном массиве.

  4. Применяем тот же алгоритм рекурсивно к левой и правой подмассивам.

  5. Когда подмассивы становятся размером 1 элемент — рекурсия останавливается, массив отсортирован.

Примечание

Асимптотическая сложность:

  • Среднее и лучшее время: O(n log n) — обычно работает очень быстро.

  • Худший случай: O(n²) — если опорный элемент каждый раз выбирается неудачно (например, в уже отсортированном массиве).

  • Память: O(log n) — на стек рекурсии.

Совет

Quick Sort — стандартный алгоритм во многих библиотеках. Например, метод Arrays.sort() в Java для примитивов использует разновидность быстрой сортировки (Dual-Pivot Quicksort).

Чтобы понять этот пример, нужно знать следующие темы Java: методы Java, цикл for в Java, массивы в Java.

Quicksort на Java

Алгоритм быстрой сортировки основан на подходе «разделяй и властвуй», где массив делится на подмассивы выбором опорного (pivot) элемента.

При разделении массива опорный элемент должен быть размещён так, чтобы элементы меньше опорного находились слева, а элементы больше — справа.

Тот же процесс продолжается для левого и правого подмассивов. Наконец, отсортированные элементы объединяются в один отсортированный массив.

Пример: программа на Java для реализации быстрой сортировки

import java.util.Arrays;

class Quicksort {

  // method to find the partition position
  static int partition(int array[], int low, int high) {

    // choose the rightmost element as pivot
    int pivot = array[high];

    // pointer for greater element
    int i = (low - 1);

    // traverse through all elements
    // compare each element with pivot
    for (int j = low; j < high; j++) {
      if (array[j] <= pivot) {

        // if element smaller than pivot is found
        // swap it with the greater element pointed by i
        i++;

        // swapping element at i with element at j
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }

    }

    // swap the pivot element with the greater element specified by i
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;

    // return the position from where partition is done
    return (i + 1);
  }

  static void quickSort(int array[], int low, int high) {
    if (low < high) {

      // find pivot element such that
      // elements smaller than pivot are on the left
      // elements greater than pivot are on the right
      int pi = partition(array, low, high);

      // recursive call on the left of pivot
      quickSort(array, low, pi - 1);

      // recursive call on the right of pivot
      quickSort(array, pi + 1, high);
    }
  }

  public static void main(String args[]) {

    int[] data = { 8, 7, 2, 1, 0, 9, 6 };
    System.out.println("Unsorted Array");
    System.out.println(Arrays.toString(data));

    int size = data.length;

    // call quicksort() on array data
    quickSort(data, 0, size - 1);

    System.out.println("Sorted Array in Ascending Order ");
    System.out.println(Arrays.toString(data));
  }
}

Вывод:

Unsorted Array
[8, 7, 2, 1, 0, 9, 6]
Sorted Array in Ascending Order
[0, 1, 2, 6, 7, 8, 9]

Здесь элементы массива отсортированы по возрастанию. Если мы хотим отсортировать элементы по убыванию, то внутри цикла for нужно изменить код так:

// the less than sign is changed to greater than
if (array[j] >= pivot) {

Важно

Ключевая идея Quick Sort — функция partition(). Она за один проход по массиву расставляет элементы так, что опорный элемент попадает на своё «правильное» место. Именно поэтому после partition() рекурсию запускают слева и справа от опорного — сам он уже на своём месте навсегда.