63
правки
Изменения
Нет описания правки
|$O(n \log \log n)$
|Очень сложная сортировка, основанная на принадлежности ключей к целым числам. использует экспоненциальное поисковое дерево Андерсона.
|- align = "center"
|[[Сортировка Шелла| Сортировка Шелла <br>(Shellsort)]]
|$O(n\log^2{n})$
|Зависит от выбора шага
|$O(n^2)$
|$O(1)$
|Нет
|$O(n^2)$
|Является улучшением сортировки вставками, сортируем между собой элементы, стоящие на кратных нашему шагу местах.
|- align = "center"
|[[Терпеливая сортировка| Терпеливая сортировка <br>(Patience sorting)]]
|$O(n\log{n})$
|$O(n\log{n})$
|$O(n\log{n})$
|$O(n)$
|Нет
|$O(n\log{n})$
|Раскидываем элементы массива по стопкам, после чего строим двоичную кучу из стопок. Позволяет также вычислить длину наибольшей возрастающей подпоследовательности данного массива.
|- align = "center"
|[[Timsort| Timsort]]
|$O(n)$
|$O(n\log{n})$
|$O(n\log{n})$
|$O(n)$
|Да
|$O(n\log{n})$
|Гибрид сортировки слиянием. Разбиваем массив на подмассивы фиксированной длины и сортируем каждый подмассив любой устойчивой сортировкой. После чего объединяем отсортированные подмассивы модифицированной сортировкой слиянием.
|- align = "center"
|[[Smoothsort| Плавная сортировка <br>(Smoothsort)]]
|$O(n)$
|$O(n\log{n})$
|$O(n\log{n})$
|$O(1)$
|Нет
|$O(n\log{n})$
|Модификация сортировки кучей.
|}
== Ссылки Источники информации==
[http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 Википедия {{- --}} Алгоритмы сортировки]
</wikitex>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
