3622
правки
Изменения
м
Постройка Построение кучи занимает <tex>O(n)</tex>. Почти упорядоченный массив сортировка вставками может отсортировать <tex> O(n)</tex>, но в худшем случае за <tex>O(n^2)</tex> в худшем.
Сам массив же будет выглядеть Массив выглядит следующим образом:
Сам массив же Массив будет выглядеть следующим образом:
→Сложность
Достоинства:
*В отличии отличие от сортировки кучей, на почти отсортированных массивах работает быстрее, чем на случайных.
*В силу использования сортировки вставками, которая просматривает элементы последовательно, использование кэша гораздо эффективнее.
Недостатки:
=== Сложность ===
Таким образом в худшем случае сложность JSort является , наихудшая оценка Jsort {{---}} <tex>O(n^2)</tex>.
=== Пример ===
| [[Файл:HeapW.png|400px]]
|}
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:HeapM.png|400px]]
| [[Файл:HeapWU.png|400px]]
|}
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:HeapMU.png|400px]]
