Быстрая сортировка — это алгоритм «разделяй и властвуй», который выбирает опорный элемент из массива и разбивает остальные элементы на два подмассива в зависимости от того, меньше они или больше опорного. Затем подмассивы сортируются рекурсивно. Этапы опорного выбора и разделения могут выполняться на месте, что делает быструю сортировку эффективным алгоритмом сортировки с пространственной сложностью O(log n). Вот реализация на JavaScript:
function quickSort(arr, left = 0, right = arr.length - 1) { if (left < right) { let pivotIndex = pivot(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex + 1, right); } return arr; } function pivot(arr, start = 0, end = arr.length - 1) { let pivot = arr[start]; let swapIndex = start; for (let i = start + 1; i <= end; i++) { if (pivot > arr[i]) { swapIndex++; [arr[swapIndex], arr[i]] = [arr[i], arr[swapIndex]]; } } [arr[start], arr[swapIndex]] = [arr[swapIndex], arr[start]]; return swapIndex; }
Объяснение
function quickSort(arr, left = 0, right = arr.length - 1) {
Это основная функция, реализующая алгоритм быстрой сортировки. Он принимает массив arr
в качестве входных данных и необязательные параметры left
и right
, которые указывают начальный и конечный индексы части массива, подлежащей сортировке. Если left
и right
не указаны, сортируется весь массив.
if (left < right) {
Эта строка проверяет, есть ли еще элементы в той части массива, которую необходимо отсортировать. Если left >= right
, это означает, что остался только один элемент или нет элементов, что означает, что часть массива уже отсортирована.
let pivotIndex = pivot(arr, left, right);
Эта строка вызывает функцию pivot
, передавая в качестве аргументов массив arr
и индексы left
и right
. Функция pivot
возвращает индекс опорного элемента, который используется для разделения массива на два подмассива.
quickSort(arr, left, pivotIndex - 1);
Эта строка сортирует подмассив с левой стороны элемента поворота. Часть массива, подлежащая сортировке, обозначается индексами left
и pivotIndex - 1
.
quickSort(arr, pivotIndex + 1, right);
Эта строка сортирует подмассив справа от элемента поворота. Часть массива, подлежащая сортировке, обозначается индексами pivotIndex + 1
и right
.
} return arr; }
Наконец, эта строка возвращает отсортированный массив.
Теперь давайте посмотрим на функцию pivot
:
function pivot(arr, start = 0, end = arr.length - 1) {
Это функция pivot
, которая используется для поиска опорного элемента в части массива, обозначенной start
и end
.
let pivot = arr[start];
Эта строка выбирает первый элемент в части массива в качестве элемента поворота.
let swapIndex = start;
Эта строка создает переменную swapIndex
и инициализирует ее значением start
. swapIndex
используется для отслеживания положения поворотного элемента по мере его перемещения в конечное положение.
for (let i = start + 1; i <= end; i++) {
Эта строка запускает цикл for
, который перебирает элементы в части массива, начиная со второго элемента. Цикл продолжается до тех пор, пока i
не станет больше end
.
if (pivot > arr[i]) {
Эта строка проверяет, меньше ли текущий элемент arr[i]
опорного элемента pivot
. Если это так, swapIndex
увеличивается, а текущий элемент arr[i]
и элемент swapIndex
меняются местами.
swapIndex++; [arr[swapIndex], arr[i]] = [arr[i], arr[swapIndex]]; } }
Эта строка увеличивается
Аналогия: быструю сортировку можно сравнить с тем, как вы сортируете колоду карт, выбирая случайную карту и помещая все карты, которые меньше ее, слева, а все карты, которые больше ее, — справа, а затем повторяя процесс для каждую подколоду, пока у вас не будет отсортированной колоды.
Ограничения:
- Производительность быстрой сортировки зависит от выбора опорного элемента. Если опорная точка выбрана неправильно, например, если опорная точка является самым большим или самым маленьким элементом в массиве, алгоритм может привести к временной сложности O (n²) в худшем случае.
- Быстрая сортировка не является стабильной, а это означает, что относительный порядок одинаковых элементов может измениться после сортировки.
- Быстрая сортировка может быть уязвима для переполнения стека, если глубина рекурсии слишком велика.