-10%
-40%
Профессии со скидками и подарки от Хекслета
Покупайте себе, дарите друзьям!

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

Ответы
Аватар пользователя Вячеслав Межуревский
Вячеслав Межуревский
27 сентября 2022

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

Алгоритм:

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

Реализация:

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));
}
Добавьте ваш ответ

Рекомендуемые курсы

утверждения
jest
матчеры
юнит-тесты
14 часов
Посмотреть
middlewares
redux-forms
actions
reselect
5 часов
Посмотреть
промисы
event loop
обработка ошибок
таймеры
18 часов
Посмотреть