Изучите сложный алгоритм за пять минут: сортировка по холму

GitHub JavaScript Язык программирования

предисловие

Поскольку многие вопросы по алгоритмам на LeetCode включают в себя некоторые базовые структуры данных, чтобы лучше понять анимацию некоторых сложных вопросов, которые будут обновлены позже, запущена новая серия — «Графические структуры данных», в которой анимация в основном используется для описания общих структуры данных и алгоритмы. Эта серия включает в себя десятки статей о десяти сортировках, кучах, очередях, деревьях, поиске объединения, графах и так далее.

Сортировка холмов

Сортировка по Хиллу, также известная как алгоритм сортировки с уменьшением приращения, является более эффективной и улучшенной версией сортировки вставками. Но сортировка Хилла — неустойчивый алгоритм сортировки.

Сортировка по Хиллу — это усовершенствованный метод, основанный на следующих двух свойствах сортировки вставками:

  • Сортировка вставками имеет высокую эффективность при работе с почти отсортированными данными, то есть может достигать эффективности линейной сортировки;
  • Но сортировка вставками, как правило, неэффективна, поскольку сортировка вставками может перемещать данные только по одному биту за раз;

Основная идея сортировки Хилла состоит в том, чтобы сначала разделить всю последовательность сортируемых записей на несколько подпоследовательностей для прямой сортировки вставками, а когда записи во всей последовательности «в основном упорядочены», выполнить прямую сортировку вставками для всех записи по очереди.

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

  1. Выберем инкрементальную последовательность t1, t2, ..., tk, где ti > tj, tk = 1;

  2. Отсортировать последовательность k раз по количеству последовательностей k;

  3. Для каждой сортировки, согласно соответствующему увеличению Ti, последовательность для сортировки делится на несколько подпоследовательностей длины M, а каждая субматарь непосредственно вставляется и отсортирован. Только когда коэффициент приращения составляет 1, вся последовательность обрабатывается как таблица, а длина таблицы - длина всей последовательности.

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

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

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

  1. Во-первых, выберите интервал приращения = 10/2, уменьшите приращение и продолжайте в том же духе, что и приращение = зазор/2.

  2. Начальный приращение зазор = 10/2 = 5, и весь массив разбивается на 5 групп.

  3. Разделены на [8, 3], [9, 5], [1, 4], [7, 6], [2, 0] по цвету

  4. Используйте сортировку вставками, описанную в предыдущем разделе, для этих 5 отдельных групп.

  5. В результате можно обнаружить, что все относительно небольшие элементы в этих пяти группах смещены вперед.

  6. Уменьшить интервал приращения = 5/2 = 2, весь массив разбит на 2 группы

  7. [3, 1, 0, 9, 7], [5, 6, 8, 4, 2]

  8. Используйте сортировку вставками, описанную в предыдущем разделе, для двух отдельных групп.

  9. На данный момент порядок всего массива очевиден

  10. Затем уменьшите интервал приращения = 2/2 = 1, весь массив будет разделен на 1 группу

  11. [0, 2, 1, 4, 3, 5, 7, 6, 9, 0]

  12. В этот момент требуется только простая тонкая настройка приведенной выше последовательности, и весь массив можно отсортировать без большого количества операций перемещения.

Код

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

Реализация кода C++

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

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

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

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

Вы можете следить за официальной учетной записью, чтобы узнать алгоритм за пять минут для дополнительной сортировки контента.

Категории