Сортировка — очень распространенная проблема в работе и жизни. Сейчас есть относительно зрелые технологии сортировки, которые широко используются в различных языках программирования или базах данных. Различные алгоритмы сортировки имеют разную производительность и применимые сценарии. В следующем видео сравнивается производительность 9 алгоритмов сортировки. Алгоритмы сортировки: сортировка выбором, сортировка по холму, сортировка вставками, сортировка слиянием, быстрая сортировка, сортировка кучей, пузырьковая сортировка, сортировка гребнем и сортировка коктейлей.
Визуализация и сравнение девяти алгоритмов сортировки
Пузырьковая сортировка
Пузырьковая сортировка — это обменная сортировка, основная идея которой состоит в том, чтобы сравнивать ключевые слова соседних записей попарно, и если они перевернуты, то они будут обмениваться до тех пор, пока не останется перевернутых записей.
В лучшем случае сама последовательность отсортирована, и требуется n - 1 сравнений, в худшем - сама последовательность в обратном порядке и n(n-1)/2 сравнений. Таким образом, общая временная сложность пузырьковой сортировки составляет O (n ^ 2).
сортировка выбором
Основная идея сортировки выбором (Selection sort) состоит в том, чтобы выбрать запись с наименьшим (или наибольшим) ключевым словом среди n - i + 1 (i = 1, 2, ***, n - 1) записей в качестве order i-я запись последовательности до тех пор, пока все элементы не будут отсортированы. Сортировка выбором — нестабильный алгоритм сортировки.
Временная сложность сортировки выбором составляет O(n^2), но ее производительность немного выше, чем у пузырьковой сортировки.
Сортировка вставками
Сортировка вставками аналогична сортировке игральных карт.Основная операция состоит в том, чтобы вставить запись в упорядоченную последовательность, которая уже была отсортирована, чтобы получить упорядоченную последовательность с количеством записей плюс один.
Временная сложность сортировки вставками составляет O(n^2), что является стабильным методом сортировки и подходит для сортировки с небольшим числом.
Сортировка коктейлей
Коктейльная сортировка — разновидность пузырьковой сортировки. Сначала найдите наименьшее число, поставьте его первым, затем найдите наибольшее число и поставьте последним. Затем найдите второе наименьшее число и подставьте его под вторую цифру, а затем найдите второе по величине число и подставьте его под предпоследнюю цифру. И так до тех пор, пока не будет произведена сортировка.
Временная сложность сортировки коктейлей составляет O (n ^ 2).
Сортировка холмов
Сортировка Шелла — это своего рода сортировка вставками, являющаяся усовершенствованием алгоритма сортировки с прямым вставкой. Основная идея состоит в том, чтобы сформировать подпоследовательность записей, разделенных определенным приращением d, и сделать эту подпоследовательность в основном упорядоченной сортировкой вставками, а затем уменьшить приращение, чтобы продолжить сортировку.
При работе в качестве первого приращения берется целое число d1, меньшее n, все записи разбиваются на d1 групп, и все записи, расстояние которых кратно dl, помещаются в одну группу. Сначала выполняем сортировку прямым вставками в каждой группе, затем берем второе приращение d2
Временная сложность сортировки Хилла может достигать O(n^(3/2)), что лучше, чем у предыдущих алгоритмов.
гребенчатая сортировка
Сортировка гребнем очень похожа на сортировку Хилла. Сортировка холмом — это оптимизация, основанная на прямой сортировке вставками, а сортировка гребнем — это оптимизация, основанная на пузырьковой сортировке, то есть записи, разделенные определенным приращением d, образуют подпоследовательность и сортируются пузырьковой сортировкой. а затем уменьшите приращение, чтобы продолжить сортировку.
Временная сложность гребенчатой сортировки составляет O(nlogn).
Сортировка слиянием
Сортировка слиянием (MERGE-SORT) — это алгоритм «разделяй и властвуй» и эффективный алгоритм сортировки, основанный на операции слияния. Обычно используемая двусторонняя сортировка слиянием предполагает, что исходная последовательность имеет n записей, которые можно рассматривать как n подпоследовательностей длины 1. Слиянием попарно можно получить n/2 подпоследовательностей длины 2 или 1. Слияние,** ****, пока не будет получена упорядоченная последовательность длины n.
Временная сложность сортировки слиянием составляет O(nlogn), что является эффективным и стабильным алгоритмом.
быстрая сортировка
Быстрая сортировка — это усовершенствование пузырьковой сортировки. Основная идея состоит в том, чтобы разделить сортируемые записи на две независимые части с помощью однопроходной сортировки, причем записи в одной части меньше, чем в другой части, а затем выполнить быструю сортировку по этим двум частям соответственно и, наконец, реализовать сортировку. всей последовательности.
Временная сложность быстрой сортировки составляет O(nlogn), что является нестабильным алгоритмом сортировки;
сортировка кучей
Куча — это полное бинарное дерево со следующими свойствами:
1. Значение каждого узла больше или равно значению его левого и правого дочерних узлов, что называется большой верхней кучей;
2. Значение каждого узла меньше или равно значению его левого и правого дочерних узлов, что называется малой верхней кучей.
Сортировка кучей относится к алгоритму сортировки, разработанному с использованием структуры данных кучи. Основная идея состоит в том, чтобы построить последовательность для сортировки в большой верхней куче.В это время максимальное значение последовательности является верхним элементом очереди, поместить этот элемент в конец, а затем продолжить построение большой вершины куча для оставшихся n - 1 элементов, пока сортировка не будет завершена.
Временная сложность сортировки кучи составляет O(nlogn), и она не подходит для небольшого количества последовательностей из-за необходимости построения кучи.
Рекомендуемое чтение
Для глубокого понимания типов перечисления Java достаточно этой статьи.
[Java Technology] Инвентаризация очередей в Java
[Изучение фреймворка] Весенняя тема 01. Контейнер IoC и его принцип
Общие функции динамического SQL MyBatis
В Java 9 добавлены 3 новые языковые функции.
Делитесь заметками об исследованиях и техническими резюме, охватывающими технологию Java, архитектуру программного обеспечения, передовые технологии, платформы с открытым исходным кодом, структуры данных и алгоритмы, идеи программирования и другие области. Эта статья была впервые опубликована в публичном аккаунте WeChat «Backend Development».
WeChat.QQ.com/day/hu О KT XE7…(автоматическое распознавание QR-кода)