Поддержим ваш первый шаг:
-10% на профессии и специальные условия до 31 мая

Как сделать быструю сортировка массива на 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));
}
4 0
Аватар пользователя Aleksey
Aleksey
05 апреля 2023

Для примера быстрой сортировки числового массива 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']
2 1
Бесплатно
Основы JavaScript
Теория и практика с нуля
Перейти к курсу
Поможем с выбором
Если у вас есть вопросы о формате или вы не знаете, что выбрать, оставьте свой номер — мы позвоним и ответим на все вопросы
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»