Быстрая сортировка — это алгоритм «разделяй и властвуй», который выбирает опорный элемент из массива и разбивает остальные элементы на два подмассива в зависимости от того, меньше они или больше опорного. Затем подмассивы сортируются рекурсивно. Этапы опорного выбора и разделения могут выполняться на месте, что делает быструю сортировку эффективным алгоритмом сортировки с пространственной сложностью O(log n). Вот реализация на JavaScript:

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

function pivot(arr, start = 0, end = arr.length - 1) {
  let pivot = arr[start];
  let swapIndex = start;
  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      swapIndex++;
      [arr[swapIndex], arr[i]] = [arr[i], arr[swapIndex]];
    }
  }
  [arr[start], arr[swapIndex]] = [arr[swapIndex], arr[start]];
  return swapIndex;
}

Объяснение

function quickSort(arr, left = 0, right = arr.length - 1) {

Это основная функция, реализующая алгоритм быстрой сортировки. Он принимает массив arr в качестве входных данных и необязательные параметры left и right, которые указывают начальный и конечный индексы части массива, подлежащей сортировке. Если left и right не указаны, сортируется весь массив.

  if (left < right) {

Эта строка проверяет, есть ли еще элементы в той части массива, которую необходимо отсортировать. Если left >= right, это означает, что остался только один элемент или нет элементов, что означает, что часть массива уже отсортирована.

    let pivotIndex = pivot(arr, left, right);

Эта строка вызывает функцию pivot, передавая в качестве аргументов массив arr и индексы left и right. Функция pivot возвращает индекс опорного элемента, который используется для разделения массива на два подмассива.

    quickSort(arr, left, pivotIndex - 1);

Эта строка сортирует подмассив с левой стороны элемента поворота. Часть массива, подлежащая сортировке, обозначается индексами left и pivotIndex - 1.

    quickSort(arr, pivotIndex + 1, right);

Эта строка сортирует подмассив справа от элемента поворота. Часть массива, подлежащая сортировке, обозначается индексами pivotIndex + 1 и right.

  }
  return arr;
}

Наконец, эта строка возвращает отсортированный массив.

Теперь давайте посмотрим на функцию pivot:

function pivot(arr, start = 0, end = arr.length - 1) {

Это функция pivot, которая используется для поиска опорного элемента в части массива, обозначенной start и end.

  let pivot = arr[start];

Эта строка выбирает первый элемент в части массива в качестве элемента поворота.

  let swapIndex = start;

Эта строка создает переменную swapIndex и инициализирует ее значением start. swapIndex используется для отслеживания положения поворотного элемента по мере его перемещения в конечное положение.

  for (let i = start + 1; i <= end; i++) {

Эта строка запускает цикл for, который перебирает элементы в части массива, начиная со второго элемента. Цикл продолжается до тех пор, пока i не станет больше end.

    if (pivot > arr[i]) {

Эта строка проверяет, меньше ли текущий элемент arr[i] опорного элемента pivot. Если это так, swapIndex увеличивается, а текущий элемент arr[i] и элемент swapIndex меняются местами.

      swapIndex++;
      [arr[swapIndex], arr[i]] = [arr[i], arr[swapIndex]];
    }
  }

Эта строка увеличивается

Аналогия: быструю сортировку можно сравнить с тем, как вы сортируете колоду карт, выбирая случайную карту и помещая все карты, которые меньше ее, слева, а все карты, которые больше ее, — справа, а затем повторяя процесс для каждую подколоду, пока у вас не будет отсортированной колоды.

Ограничения:

  1. Производительность быстрой сортировки зависит от выбора опорного элемента. Если опорная точка выбрана неправильно, например, если опорная точка является самым большим или самым маленьким элементом в массиве, алгоритм может привести к временной сложности O (n²) в худшем случае.
  2. Быстрая сортировка не является стабильной, а это означает, что относительный порядок одинаковых элементов может измениться после сортировки.
  3. Быстрая сортировка может быть уязвима для переполнения стека, если глубина рекурсии слишком велика.