Алгоритмы, не основанные на сравнениях

Список алгоритмов сортировки

В этой таблице n — это количество записей, которые необходимо упорядочить, а k — это количество уникальных ключей.

Алгоритмы устойчивой сортировки

· Сортировка пузырьком (англ. Bubble sort) — сложность алгоритма: O(n ²); для каждой пары индексов производится обмен, если элементы расположены не по порядку. Павлов

· Сортировка перемешиванием (Шейкерная, Cocktail sort, bidirectional bubble sort) — Сложность алгоритма: O(n ²) Высоцкий

· Гномья сортировка — имеет общее с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — O(n ²). Ковенский

· Сортировка вставками (метод простых ставок)(Insertion sort) — Сложность алгоритма: O(n ²); определяем где текущий элемент должен находиться в упорядоченном списке и вставляем его туда Новикова

· Сортировка вставками (метод двухпутевых вставок)(Insertion sort) — Сложность алгоритма: O(n ²); определяем где текущий элемент должен находиться в упорядоченном списке и вставляем его туда Стрельцов

· Блочная сортировка (Корзинная сортировка, черпачная сортировка, 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 ²); поиск наименьшего или наибольшего элемента и помещения его в начало или конец упорядоченного списка Веркович

· Сортировка Шелла (Shell sort) — Сложность алгоритма: O(n log² n); попытка улучшить сортировку вставками Марковский

· Сортировка расчёской (Comb sort) — Сложность алгоритма: O(n log n)

· Пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка

· Плавная сортировка (Smoothsort) — Сложность алгоритма: O(n log n)

· Быстрая сортировка (Quicksort) — Сложность алгоритма: O(n log n) — среднее время, O(n ²) — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине Иванин

· 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 ³); рекурсивная версия требует дополнительно O(n ²) памяти

· Bead Sort — O(n) or O(√ n), требуется специализированное аппаратное обеспечение

· Блинная сортировка (Pancake sorting) — O(n), требуется специализированное аппаратное обеспечение

Алгоритмы, не основанные на сравнениях

· Блочная сортировка (Корзинная сортировка, Bucket sort)

· Лексикографическая или поразрядная сортировка (Radix sort)

· Сортировка подсчётом (Counting sort)