Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-03-10

1 Теги: quicksort, алгоритмы сортировки, php программирование, сортировка на php, быстрая сортировка

2 В этой статье поговорим оБыстрой сортировке(quicksort). Почему именно она? На мой взгляд, эта сортировка отлично подходит для решения повседневных задач. Ниже я приведу принцип данной сортировки и две её реализации - наPHPиJavaScript.

3 Wiki говорит, что быстрая сортировка была придумана английским информатиком ЧарльзомХоаромв 1960 году.

4 Сортировка работает следующим образом:

5 1) Выбирается опорный элемент. Его можно выбрать случайно, обозначить его последним или средним - это всё не будет влиять на эффективность.

6 2) Массив перестраивается следующим образом: слева от опорного алгоритма находятся элементы, которые меньше его или равны ему, справа - элементы, которые больше него.

7 На каждой итерации мы выполняем следующие действия а) выбираем два индексаlowиhigh, равные крайнему левому и крайнему правому элементам входного массива; б) вычисляем индекс опорного элементаmiddle; в) увеличиваемlowпоследовательно до тех пор, пока элемент с индексом low не будет больше или равен опорному; г) уменьшаем high последовательно до тех пор, пока элемент с индексом high не будет меньше или равен опорному; д1) если low = high, то мы нашли середину входного массива; д2) если low < high, то мы меняем эти элементы местами.

8 3) Далее мы начинаем рекурсивно упорядочивать полученные два массива из элементов, лежащих справа и слева от опорного элемента соответственно.

9 4) Рекурсивное обращение продолжается до тех пор, пока все входные наборы не будут содержать один или два элемента.

10 Данная сортировка - это глубокое улучшение сортировки "пузырьком". Она является одним из самых быстродействующих алгоритмов сортировки общего назначения.

11 <h2>От теории к практике</h2>

12 Рассмотрим реализацию на PHP. В функцию quickSort передаём три параметра: массив (по ссылке), левую границу и правую границу. Сразу же определяем$middle- опорный элемент. Мы возьмём в качестве него средний элемент массива. Далее начинаем два циклических обхода справа и слева до нахождения бОльшего и мЕньшего элементов относительно опорного, перебрасываем их. Затем рекурсивно вызываем quickSort для двух полученных массивов. Здесь всё достаточно просто, а код функции будет выглядеть вот так:

13 function quickSort(&$arr, $low, $high) { $i = $low; $j = $high; $middle = $arr[ ( $low + $high ) / 2 ]; // middle - опорный элемент; в нашей реализации он находится посередине между low и high do { while($arr[$i] < $middle) ++$i; // ищем элементы для правой части while($arr[$j] > $middle) -$j; // ищем элементы для левой части if($i <= $j){ // перебрасываем элементы $temp = $arr[$i]; $arr[$i] = $arr[$j]; $arr[$j] = $temp; // следующая итерация $i++; $j--; } } while($i < $j); if($low < $j){ // рекурсивно вызываем сортировку для левой части quickSort($arr, $low, $j); } if($i < $high){ // рекурсивно вызываем сортировку для правой части quickSort($arr, $i, $high); } }На JavaScript функция не будет сильно отличаться структурно, однако имеются некоторые моменты, касающиеся самого языка. В определении опорного элемента следует принудительно использовать округление, дабы не получить дробный индекс. Массив передается по ссылке по умолчанию, так что хитрить с приведением типов не следует.

14 function quickSort(arr, low, high) { var i = low; var j = high; var middle = arr[ Math.round(( low + high ) / 2) ]; // middle - опорный элемент; в нашей реализации он находится посередине между low и high do { while(arr[i] < middle) { ++i; // ищем элементы для правой части } while(arr[j] > middle) { --j; // ищем элементы для левой части } if(i <= j){ // перебрасываем элементы var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; // следующая итерация i++; j--; } } while(i < j); if(low < j){ // рекурсивно вызываем сортировку для левой части quickSort(arr, low, j); } if(i < high){ // рекурсивно вызываем сортировку для правой части quickSort(arr, i, high); } }Рабочий пример сортировки можно посмотреть<a>тут</a>.