Алгоритмы JavaScript: быстрая сортировка

Быстрая сортировка - более эффективный алгоритм поиска, чемсортировка по выбору,в большинстве случаев, и он использует рекурсию.

Рекурсия означает, что мы вызываем функцию из той же самой функции. Иногда это очень полезная практика, и это один из таких случаев.

Я сказал «в большинстве случаев», потому что, как мы увидим, в худшем случае пузырьковая сортировка может занять то же время, что и сортировка по выбору:O(n^2). Но в лучшем случае он будет работать наO(n log n), который находится посередине междуO(n)иO(n^2).

Как это работает? Учитывая массив, мы выбираем элемент с именемвращаться. Затем мы получаем все элементы меньше, чем точка поворота, и элементы больше, чем точка поворота.

Затем мы выполняем ту же операцию с массивом 2, который составляет меньшие и большие элементы.

Код легче увидеть, чем описать:

const quickSort = (originalList) => {
  const list = [...originalList]

if (list.length < 2) { return list }

const pivot = list[0]

const smaller = list.filter((item) => item < pivot) const bigger = list.filter((item) => item > pivot)

return […quickSort(smaller), pivot, …quickSort(bigger)] }

В этом случае я выбрал точку поворота как первый элемент в массиве, но это также может быть элемент посередине, например:

const pivot = list[Math(floor(list.length / 2)]

Обратите внимание, как мы сначала копируем массив, поэтому вызываемquickSort()не изменяет исходный массив, а просто возвращает новый отсортированный массив:

const a = [1, 6, 3, 4, 5, 1, 0, 4, 8]

console.log(quickSort(a)) //[0, 1, 1, 3, 4, 4, 5, 6, 8 console.log(a) //[1, 6, 3, 4, 5, 1, 0, 4, 8]

Скачать мою бесплатнуюРуководство для начинающих по JavaScript


Больше руководств по js: