63
правки
Изменения
Нет описания правки
|$O(n^2)$
|На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован.
|- align = "center"
|[[Сортировка Шелла| Сортировка Шелла <br>(Shellsort)]]
|$O(n\log^2{n})$
|Зависит от выбора шага
|$O(n^2)$
|$O(1)$
|Нет
|$O(n^2)$
|Является модификацией сортировки вставками, сортируем между собой элементы, стоящие на кратных нашему шагу местах.
|- align = "center"
|[[Сортировка выбором| Сортировка выбором<br> (Selection Sort)]]
|$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"
|[[Сортировка кучей|Сортировка кучей <br>(Heap Sort)]]
|$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})$
|Модификация сортировки кучей. Вместо двоичной кучи используем K-ую кучу Леонардо.
|- 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"
|[[Дерево поиска, наивная реализация|Сортировка с помощью бинарного дерева <br>(Tree Sort)]]
|$O(n \log \log n)$
|Очень сложная сортировка, основанная на принадлежности ключей к целым числам. использует экспоненциальное поисковое дерево Андерсона.
|}
