Пирамидальная сортировка (Heapsort)
Алгоритм:
Строим дерево из последовательности, сразу “сортируя” все элементы от большего(корня) к меньшему(листья).
В итоге получаем новый массив. Выталкиваем самый большой элемент на верх и меняем с самым правым листом и удаляем его.
Достоинства
Имеет доказанную оценку худшего случая O(nlogn).
Требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).
Недостатки
Сложен в реализации.
Неустойчив — для обеспечения устойчивости нужно расширять ключ.
На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.
Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.
Сортировка с помощью двоичного дерева
Алгоритм:
Построение двоичного дерева.
Сборка результирующего массива путём обхода узлов в необходимом порядке следования ключей.
Турнирная сортировка
Алгоритм:
Строим подобие бинарного дерева, таким образом что самый маленький элемент попадает в корень.
Как только наименьший элемент обнаружен записываем его в массив, а в дереве присваиваем ему
.И так до тез пор пока все элементы не станут .
Поразрядная сортировка
Алгоритм:
Составляем таблицу где последовательность отсортирована в по последнему разряду(0).
Дальше составляем таблицу для следующего разряда(1).
И так до самого большого разряда числа в последовательности.
Цифры в разрядах |
0-ой разряд |
1-ый разряд |
0 |
|
|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
|
6 |
|
|
7 |
|
|
8 |
|
|
9 |
|
|
Буква в раз-ах |
0-ой разряд |
1-ый разряд |
2-ой разряд |
3-ий разряд |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
