Когда дело доходит до сортировки элементов путем их сравнения, сортировка слиянием является одним из самых естественных подходов. Это естественно, поскольку он просто делит список на два равных подсписка, а затем сортирует эти два раздела, применяя одно и то же правило. Это типичный алгоритм «разделяй и властвуй», и он следует интуитивному подходу, позволяющему ускорить процесс сортировки за счет сокращения количества сравнений. Однако существуют другие алгоритмы сортировки «разделяй и властвуй», которые не следуют схеме сортировки слиянием, сохраняя при этом аналогичный уровень успеха. Такой алгоритм является быстрой сортировкой.
обзор
Еще в 1960 году CAR Hoare разработал блестящий алгоритм сортировки. Обычно быстрая сортировка состоит из нескольких очень простых шагов. Сначала мы должны выбрать элемент из списка (называемый сводкой), затем мы должны поместить все элементы со значением, меньшим, чем стержень, в левой части сводки, а все элементы со значением, превышающим значение стержня в правой части. , После этого мы должны повторить эти шаги для левого и правого подсписков. Это быстрая сортировка! Просто и элегантно!
Это чистый подход типа «разделяй и властвуй», подобный сортировке слиянием, но, хотя сложная задача сортировки слиянием заключалась в объединении отсортированных подсписков, при быстрой сортировке следует учитывать и другие вещи.
Прежде всего, лучшим выбором для разворота является узкое место. На самом деле все зависит от этой оси. Представьте, что вы выбираете наибольшее значение из списка — тогда вы должны поместить все остальные элементы списка в «левый» подсписок. Если вы будете делать это на каждом этапе, вы практически попадете в худший сценарий, и это не хорошо. Дело в том, что в худшем случае быстрая сортировка не так эффективна и практически такая же медленная, как сортировка пузырьков и сортировка вставками. Хорошая вещь состоит в том, что на практике со случайно сгенерированными списками нет высокой возможности перейти к худшему случаю быстрой сортировки.
Выбор точки разворота
Конечно, лучшая точка — это средний элемент списка, оставляя список разделенным на два довольно равных подсписка. Проблема в том, что нет простого способа получить средний элемент из списка, и это замедлит алгоритм. Поэтому, как правило, мы можем получить для пивота первый или последний элемент списка.
После выбора оси все остальное просто. Поместите каждый элемент с большим значением справа и каждый элемент с меньшим значением слева. Затем мы должны отсортировать левый и правый подсписки так же, как мы делали с начальным списком.
Понятно, что с этим алгоритмом мы естественным образом вступаем в рекурсивное решение. Обычно каждый подход «разделяй и властвуй» легко реализовать с помощью рекурсии. Но поскольку рекурсия может быть тяжелой, существует итеративный подход.
Реализация
Как я уже говорил выше, рекурсивный подход является очень естественным для быстрой сортировки, поскольку он следует принципам «разделяй и властвуй». На каждом шаге мы делим список на две части и передаем эти подсписки нашей рекурсивной функции. Но рекурсия иногда опасна, поэтому итерационный подход также доступен. Обычно итеративные подходы «моделируют» рекурсию с дополнительной памятью и моделью стека, как в нашем случае. Здесь у нас есть два примера быстрой сортировки — рекурсивная и итеративная в PHP. Давайте посмотрим рекурсию на первом:
Рекурсивная быстрая сортировка
$list = array(5,3,9,8,7,2,4,1,6,5);
// recursive
function quicksort($array)
{
if (count($array) == 0) {
return array();
}
$pivot = $array[0];
$left = $right = array();
for ($i = 1; $i < count($array); $i++) {
if ($array[$i] < $pivot) {
$left[] = $array[$i];
} else {
$right[] = $array[$i];
}
}
return array_merge(quicksort($left), array($pivot), quicksort($right));
}
// 1, 2, 3, 4, 5, 5, 6, 7, 8, 9
print_r(quicksort($list));
Итеративная быстрая сортировка
$list = array(5,3,9,8,7,2,4,1,6,5);
// iterative
function quicksort_iterative($array)
{
$stack = array($array);
$sorted = array();
while (count($stack) > 0) {
$temp = array_pop($stack);
if (count($temp) == 1) {
$sorted[] = $temp[0];
continue;
}
$pivot = $temp[0];
$left = $right = array();
for ($i = 1; $i < count($temp); $i++) {
if ($pivot > $temp[$i]) {
$left[] = $temp[$i];
} else {
$right[] = $temp[$i];
}
}
$left[] = $pivot;
if (count($right))
array_push($stack, $right);
if (count($left))
array_push($stack, $left);
}
return $sorted;
}
// 1, 2, 3, 4, 5, 5, 6, 7, 8, 9
print_r(quicksort_iterative($list));
сложность
Сложность быстрой сортировки в среднем случае составляет O (n * log (n)) — так же, как сортировка слиянием. Проблема в том, что в худшем случае это O (n 2 ) — то же самое, что и пузырьковая сортировка. Очевидно, худший случай — это когда у нас уже есть отсортированный список, и мы постоянно принимаем за последний элемент списка. Но мы должны учитывать, что на практике мы не совсем используем отсортированные списки, которые мы должны сортировать снова, верно?
заявка
Quicksort — отличный алгоритм сортировки, и разработчики часто используют его, но давайте посмотрим на его плюсы и минусы.
Зачем использовать быструю сортировку
- Рекурсивная реализация проста
- В общем, его скорость такая же, как сортировка слиянием — O (n * log (n))
- Элегантное решение без хитрого слияния как слияние
Почему бы не использовать быструю сортировку
- В самом худшем случае медленно, как пузырьковая сортировка!
- Итеративная реализация не легка
- Есть более быстрые алгоритмы для некоторых наборов типов данных
Быстрая сортировка прекрасна из-за элегантной идеи, лежащей в основе ее принципов. Если у вас есть два отсортированных списка, один с элементами с большим значением из заданного значения, а другой с элементами меньшего размера, чем данное значение, вы можете просто объединить их, и вы можете быть уверены, что результирующий список будет отсортирован без необходимости особое слияние
На самом деле быстрая сортировка — это очень элегантный алгоритм сортировки общего назначения, и каждый разработчик должен быть знаком с его принципами.