Изменения
Нет описания правки
{|class="wikitable"
|+
!width="2015%"|Название !!width="108%"| Лучшее время !!width="108%"| Среднее !!width="108%"| Худшее !!width="108%"| Память !! width="108%"|Стабильность !!width="3010%| Обмены (в среднем) !! "width="35%"| Описание
|- align = "center"
|[[Сортировка пузырьком| Сортировка пузырьком <br>(Bubble Sort)]]
|$O(1)$
|Да
|$O(n^2)$
|Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами.
|- align = "center"
|$O(1)$
|Да
|$O(n^2)$
|На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован.
|- align = "center"
|$O(1)$
|Нет
|$O(n)$
|На каждом $i$-ом шаге алгоритма находим $i$-ый минимальный элемент и меняем его местами с $i$-ым элементом в массиве.
|- align = "center"
|[[Быстрая сортировка|Быстрая сортировка<br> (Quick Sort)]]
|$O(n \log n)$
|$O(n \log n)$
|$O(n^2)$<br>(маловероятно)
|$O(\log n)$<br>(стек вызовов)
|Нет
|$O(n \log n)$
|Один из самых известных и широко используемых алгоритмов сортировки. Алгоритм состоит в выборе опорного элемента, разделении массива на 2 части относительно опорного и в сортировке полученных частей.
|- align = "center"
|[[Сортировка слиянием|Сортировка слиянием <br>(Merge Sort)]]
|$O(n \log n)$
|$O(n \log n)$
|$O(n \log n)$
|$O(n)$ (обычная реализация)<br>$O(1)$<br> ([[Cортировка слиянием с использованием O(1) дополнительной памяти|модифицированная реализация]])
|Да
|$O(n \log n)$
|Алгоритм состоит в разделении массива пополам, сортировки половин и их слиянии.
|- align = "center"
|[[Сортировка кучей|Пирамидальная сортировка <br>(Heap Sort)]]
|$O(n \log n)$
|$O(n \log n)$
|$O(n \log n)$
|$O(1)$
|Нет
|$O(n \log n)$
|Строим из массива кучу, по очереди извлекаем минимум кучи.
|- align = "center"
|[[Дерево поиска, наивная реализация|Сортировка с помощью бинарного дерева <br>(Tree Sort)]]
|$O(n)$
|$O(n \log n)$
|$O(n \log n)$
|$O(n)$
|Да
|$O(n)$
|Добавляем по очереди вершины в сбалансированное дерево поиска, проходим по всем вершинам в порядке возрастания.
|- align = "center"
|[[Карманная сортировка|Карманная сортировка <br>(Bucked Sort)]]
|$O(n)$
|$O(n \log n)$
|$O(n^2)$
|$O(n)$
|Да
| -
|распихиваем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения.
|- align = "center"
|[[Цифровая сортировка|Цифровая сортировка <br>(Radix Sort)]]
|$O(n \log n)$
|$O(n \log n)$
|$O(n \log n)$
|$O(n)$
|Да
| -
|сортировка, аналогичная карманной. карманы в данном случае - цифры от 0 до 9.
|}
* Прочие сортировки.
** [[Сортировка Хэна (или Хана?)|Сортировка Хэна]] - упоротая сортировка целых чисел с оценкой $O(n \log \log n)$
</wikitex>
