143
правки
Изменения
→Сложность
Таким образом в худшем случае сложность JSort является <tex>O(n^2)</tex>, а в лучшем <tex>O(n)</tex>
=== Пример ===
Рассмотрим, массив <tex> A </tex> = <tex> (1, 2, 8, 15, 17, 20, 31, 32, 30, 2, 3, 5, 10, 11, 24 ) </tex>
Построим на этом массиве невозрастающую кучу:
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:HeapW.png|400px]]
|}
Сам массив же будет выглядеть следующим образом:
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:HeapM.png|400px]]
|}
Заметим, что начало почти упорядочено, что хорошо скажется на использовании сортировки вставками.
Построим теперь зеркальную неубывающую кучу на этом же массиве.
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:HeapWU.png|400px]]
|}
Сам массив же будет выглядеть следующим образом:
{| cellpadding="3" style="margin-left: left; margin-right: left;"
| [[Файл:HeapMU.png|400px]]
|}
Теперь и конец массива выглядит упорядоченным, применим сортировку вставками и получим отсортированный массив.
== См. также ==
