Пять минут, чтобы понять сложную сортировку: сортировка кучей

задняя часть алгоритм GitHub Язык программирования

Предварительные знания: структура кучи

Куча — это полное бинарное дерево со следующими свойствами: значение каждого узла больше или равно значению его левого и правого дочерних узлов, которое называется большой верхней кучей; или значение каждого узла меньше или равно значению его левого и правого дочерних узлов, называемому маленькой верхней кучей.

Верхняя куча

небольшой верхний ворс

сортировка кучей

Heapsort (Heapsort) относится к алгоритму сортировки, разработанному с использованием структуры данных кучи (следующая [Структура графических данных] поясняет анализ). Стекирование — это структура, которая аппроксимирует полное бинарное дерево и в то же время удовлетворяет свойству стекирования: то есть значение ключа или индекс дочернего узла всегда меньше (или больше) его родительского узла. Можно сказать, что сортировка кучей является сортировкой выбором, которая использует концепцию кучи для сортировки. Есть два метода:

  • Куча с большой вершиной: значение каждого узла больше или равно значению его дочерних узлов, которое используется для возрастания в алгоритме сортировки кучи;

  • Маленькая верхняя куча: значение каждого узла меньше или равно значению его дочерних узлов, которое используется для убывания в алгоритме сортировки кучи;

Средняя временная сложность Heapsort является ο (NLOGN).

Шаг алгоритма

  1. Создать кучу H[0...n-1];

  2. Поменять местами голову кучи (максимальное значение) и хвост кучи;

  3. Уменьшите размер кучи на 1 и вызовите shift_down(0), цель состоит в том, чтобы настроить верхние данные нового массива на соответствующую позицию;

  4. Повторяйте шаг 2, пока размер кучи не станет равным 1.

источник:GitHub.com/выпроводить его из города/js-s…

Демонстрация алгоритма

Объяснение процесса анимации сортировки

  1. Сначала сохраните все числа в куче

  2. Постройте кучу в соответствии с кучей с большой вершиной.Одной из характеристик кучи с большой вершиной является то, что данные будут выбираться от наибольшего к наименьшему, а извлеченные числа будут располагаться в обратном порядке, а числа будут отсортировано.

  3. Здесь цифра 5 идет первой

  4. Номер 2 в кучу

  5. В стек номер 7, 7 в это время является последним узлом, сравнивается с последним нелистовым узлом (т.е. числом 5), поскольку 7 больше, чем 5, 7 и 5 поэтому взаимодействуют

  6. Поместите все числа в стопку в соответствии с описанной выше операцией, а затем отрегулируйте слева направо и сверху вниз, чтобы построить большую верхнюю стопку.

  7. После завершения кучи выньте верхний элемент, поместите конечный элемент в верхнюю часть, повторно отрегулируйте структуру, чтобы она удовлетворяла определению кучи

  8. Номер 7 верхнего элемента кучи вынимается, а номер 4 последнего элемента помещается на вершину кучи.Чтобы сохранить определение большой верхней кучи, номер последнего нелистового узла 5 сравнивается с 4, а затем меняются местами два числа

  9. Повторяйте шаги регулировки + замены до тех пор, пока вся последовательность не будет в порядке.

Код

Чтобы лучше позволить читателям понять анимацию со своими знакомыми языками программирования, автор будет публиковать контрольные коды различных языков программирования, все из которых происходят из Интернета.

Реализация кода Go

Реализация кода Java

Реализация кода Python

Реализация кода JavaScript

Если вы разработчик iOS, который может быть на GithubGitHub.com/Мистер Б ООО/…Получить исходный Run Debug Run может быть более интуитивным.

Вы можете зайти в публичный аккаунтИзучите алгоритмы за 5 минутПолучите больше контента для сортировки.

Категории