Список алгоритмов сортировки
В этой таблице n — это количество записей, которые необходимо упорядочить, а k — это количество уникальных ключей.
Алгоритмы устойчивой сортировки
· Сортировка пузырьком (англ. Bubble sort) — сложность алгоритма: O(n 2); для каждой пары индексов производится обмен, если элементы расположены не по порядку. Павлов
· Сортировка перемешиванием (Шейкерная, Cocktail sort, bidirectional bubble sort) — Сложность алгоритма: O(n 2) Высоцкий
· Гномья сортировка — имеет общее с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — O(n 2). Ковенский
· Сортировка вставками (метод простых ставок)(Insertion sort) — Сложность алгоритма: O(n 2); определяем где текущий элемент должен находиться в упорядоченном списке и вставляем его туда Новикова
· Сортировка вставками (метод двухпутевых вставок)(Insertion sort) — Сложность алгоритма: O(n 2); определяем где текущий элемент должен находиться в упорядоченном списке и вставляем его туда Стрельцов
· Блочная сортировка (Корзинная сортировка, черпачная сортировка, Bucket sort) — Сложность алгоритма: O(n); требуется O(k) дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций "переставить" и "сравнить".
- Сортировка подсчётом (Counting sort) — Сложность алгоритма: O(n + k); требуется O(n + k) дополнительной памяти (простой алгоритм) Буценко
- Сортировка подсчётом (Counting sort) — Сложность алгоритма: O(n + k); требуется O(n + k) дополнительной памяти (квадратичный алгоритм)
- Сортировка слиянием (Merge sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; выстраиваем первую и вторую половину списка отдельно, а затем — сливаем упорядоченные списки(простое двухпутевое слияние)
- Сортировка слиянием (бинарное слияние) Сысун
- Сортировка слиянием (Алгоритм Пратта) Друщиц
- Сортировка с помощью двоичного дерева (англ. Tree sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти
Алгоритмы неустойчивой сортировки
· Сортировка выбором (Selection sort) — Сложность алгоритма: O(n 2); поиск наименьшего или наибольшего элемента и помещения его в начало или конец упорядоченного списка Веркович
· Сортировка Шелла (Shell sort) — Сложность алгоритма: O(n log2 n); попытка улучшить сортировку вставками Марковский
· Сортировка расчёской (Comb sort) — Сложность алгоритма: O(n log n)
· Пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
· Плавная сортировка (Smoothsort) — Сложность алгоритма: O(n log n)
· Быстрая сортировка (Quicksort) — Сложность алгоритма: O(n log n) — среднее время, O(n 2) — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине Иванин
· Introsort — Сложность алгоритма: O(n log n), сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает log(n).
· Patience sorting — Сложность алгоритма: O(n log n + k) — наихудший случай, требует дополнительно O(n + k) памяти, также находит самую длинную увеличивающуюся подпоследовательность
· Stooge sort — рекурсивный алгоритм сортировки с временной сложностью .
· Поразрядная сортировка — Сложность алгоритма: O(n · k); требуется O(k) дополнительной памяти.
· Цифровая сортировка — то же, что и Поразрядная сортировка.
Непрактичные алгоритмы сортировки
· Bogosort — O(n · n!) в среднем. Произвольно перемешать массив, проверить порядок.
· Сортировка перестановкой — O(n · n!) — худшее время. Генерируются всевозможные перестановки исходного массива и для каждой осуществляется проверка верного порядка.
· Глупая сортировка (Stupid sort) — O(n 3); рекурсивная версия требует дополнительно O(n 2) памяти
· Bead Sort — O(n) or O(√ n), требуется специализированное аппаратное обеспечение
· Блинная сортировка (Pancake sorting) — O(n), требуется специализированное аппаратное обеспечение
Алгоритмы, не основанные на сравнениях
· Блочная сортировка (Корзинная сортировка, Bucket sort)
· Лексикографическая или поразрядная сортировка (Radix sort)
· Сортировка подсчётом (Counting sort)