Как сделать быструю сортировка массива на javascript

Question

Accepted Answer

Быстрая сортировка, часто называемая qsort, один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем имеет сложность O(n\log n) обменов при упорядочении n элементов. Из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками. Не углубляясь в подробности рассмотрим простой вариант использующий рекурсию.

Алгоритм:

Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива.
Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные» и «большие».
Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

Реализация:

const quickSort = (arr) => {
  // Условие остановки, выхода из рекурсии, возвращем массив с 1 элементом
  if (arr.length < 2) return arr;
  // Выбираем опорный элемент
  let pivot = arr[0];
  // Определяем массивы для тех, что меньше и больше опорного
  const left = [];
  const right = [];

  // Проходим циклом по всем элементам из массива и разносим их в массивы созданные ранее согласно условию, больше опорного - в правый, меньше - в левый  
  for (let i = 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  // Рекурсивно повторяем процесс для новых двух массивов, текущий опорный элемент - кладем как первый в правый массив.
  return quickSort(left).concat(pivot, quickSort(right));
}

Answer

Для примера быстрой сортировки числового массива numbers можно использовать встроенный метод Array.prototype.sort(). Этот метод сортирует элементы массива в порядке возрастания или по алфавиту, если элементы являются строками. Однако, если нужно отсортировать массив в порядке убывания или по другому критерию, то можно передать в метод sort() функцию сравнения.

Пример сортировки массива чисел в порядке возрастания:

const numbers = [5, 2, 8, 1, 4];
numbers.sort((a, b) => a - b);
console.log(numbers); // [1, 2, 4, 5, 8]

Пример сортировки массива строк в порядке убывания:

const fruits = ['banana', 'apple', 'orange', 'kiwi'];
fruits.sort((a, b) => b.localeCompare(a));
console.log(fruits); // ['orange', 'kiwi', 'banana', 'apple']

Как сделать быструю сортировка массива на javascript

Похожие вопросы