Структуры данных и алгоритмы Javascript: сортировка, часть 2

Быстрая сортировка

Алгоритм Quicksort — один из самых быстрых алгоритмов сортировки больших наборов данных. Быстрая сортировка — это алгоритм «разделяй и властвуй», который рекурсивно разбивает список данных на последовательно меньшие подсписки, состоящие из меньших и больших элементов. Быстрая сортировка работает, получая опорную точку и разбивая массив вокруг нее (элементы большего размера с одной стороны и элементы меньшего размера с другой), пока все не будет отсортировано. Как показано на рисунке, как работает быстрая сортировка.

Временная сложность: O(nlog2(n)) в среднем, O(n2) в худшем случае

Пространственная сложность: O(log2(n))

Код для быстрой сортировки:

Сортировка слиянием

Алгоритм сортировки слиянием назван так потому, что он работает путем слияния отсортированных подсписков вместе, чтобы сформировать более крупный, полностью отсортированный список. Теоретически этот алгоритм должен быть прост в реализации. Нам нужны два отсортированных подмассива и третий массив, в который мы объединяем два подмассива, сравнивая элементы данных и вставляя наименьшее значение элемента. Сортировка слиянием работает путем деления массива на подмассивы до тех пор, пока каждый массив не будет содержать один элемент. Затем каждый подмассив объединяется (объединяется) в отсортированном порядке. Как показано на рисунке, как работает сортировка слиянием.

Временная сложность: O(nlog2(n))

Пространственная сложность: O(n)

Код для сортировки слиянием:

Ссылка / важная ссылка