предисловие
Поскольку многие вопросы по алгоритмам на LeetCode включают в себя некоторые базовые структуры данных, чтобы лучше понять анимацию некоторых сложных вопросов, которые будут обновлены позже, запущена новая серия — «Графические структуры данных», в которой анимация в основном используется для описания общих структуры данных и алгоритмы. Эта серия включает в себя десятки статей о десяти сортировках, кучах, очередях, деревьях, поиске объединения, графах и так далее.
быстрая сортировка
Quicksort — это алгоритм сортировки, разработанный Тони Холлом. В среднем для сортировки n элементов требуется Ο(nlogn) сравнений. В худшем случае требуется 0(n2) сравнений, но это не является обычным явлением. На самом деле быстрая сортировка обычно значительно быстрее других алгоритмов Ο(nlogn), потому что ее внутренний цикл может быть эффективно реализован на большинстве архитектур.
Быстрая сортировка использует стратегию «разделяй и властвуй», чтобы разделить список на два подсписка.
Быстрый сортировка - это типичный приложить разделить и завоевать мысли о сортировке алгоритмов. По сути, быстрый сорт должен быть пузыренным рекурсионным делением и победу на основе своего рода.
Шаг алгоритма
-
Выберите элемент из последовательности, называемый «стержнем»;
-
Измените порядок последовательности, все элементы, меньшие эталонного значения, помещаются перед эталонным значением, а все элементы, превышающие эталонное значение, помещаются в конце эталонного значения (одинаковые числа могут идти с любой стороны). После выхода из раздела эталон находится в середине последовательности. Это называется операцией раздела;
-
Рекурсивно сортировать подмассивы элементов меньше эталонного значения и подмассивы элементов больше эталонного значения;
В нижнем случае рекурсии размер последовательности равен нулю или единице, которая всегда сортируется. Хотя он продолжает повторяться, алгоритм всегда будет завершаться, потому что на каждой итерации он будет помещать по крайней мере один элемент в его последнюю позицию.
источник:GitHub.com/выпроводить его из города/js-s…
Демонстрация алгоритма
Объяснение процесса анимации сортировки
-
Во-первых, все числа в столбце операндов
-
В качестве опорной для сортировки выбираем число среди всех чисел, опорная точка обычно выбирается случайным образом, здесь для удобства демонстрации мы выбираем в качестве опорной самую правую цифру
-
После выбора точки опоры в столбце операндов выберите крайнее левое число, помеченное как левая метка, и самое правое число, помеченное как правая метка.
-
переместить левый маркер вправо
-
Остановите движение, когда левый маркер достигнет числа, превышающего точку поворота.
-
Здесь 8 > 6 , так что перестаньте двигаться
-
Затем переместите маркер справа налево
-
Остановить движение, когда правый маркер достигает числа меньше точки поворота
-
Здесь 4 > 6 , так что перестаньте двигаться
-
Когда левый и правый маркеры остановятся, измените количество маркеров
-
Таким образом, роль левого маркера состоит в том, чтобы найти число больше, чем точка опоры, а роль правого маркера состоит в том, чтобы найти число меньше, чем точка опоры.
-
Поменяв местами числа, вы можете собрать набор чисел, меньших точки опоры, в левой части последовательности и набор чисел, превышающих точку опоры, в правой части последовательности.
-
После обмена продолжайте перемещать левый маркер
-
Здесь 9 > 6 , так что перестаньте двигаться
-
Затем переместите маркер справа налево
-
Также прекращайте движение, когда правый маркер сталкивается с левым маркером.
-
Если левый и правый маркеры остановлены и оба находятся в одном и том же положении, поменяйте этот номер местами с номером поворота.
-
На этом первая операция завершена.
-
Все, что меньше 6, находится слева от 6, а все, что больше 6, — справа от 6.
-
Затем рекурсивно сделайте то же самое для обеих частей
-
полная быстрая сортировка
Код
Чтобы читатели могли лучше понять анимацию с помощью знакомых им языков программирования, автор будет публиковать справочные коды различных языков программирования, все из которых взяты из Интернета.
Реализация кода C++
Реализация кода Java
Реализация кода Python
Реализация кода JavaScript
Если вы разработчик iOS, вы можете найти его на GitHub.GitHub.com/Мистер Б ООО/…Получите более интуитивно понятный и отлаживаемый исходный код.
Вы можете следить за официальной учетной записью, чтобы узнать алгоритм за пять минут для дополнительной сортировки контента.