234
правки
Изменения
Нет описания правки
Обычно таким признаком служит лексикографический номер.
Так как данные могут хранится в разных структурах, то и алгоритмы для каждой структуры могут отличаться. Например, при хранении данных в списке, нежели чем в массиве, сортировка слиянием потребует $O(n^2)$ времени и $O(1)$ памяти против $O(n \log n)$ и $O(n)$ с использованием массива; а вот сортировка пузырьком не изменится.
Также есть алгоритмы параллельной сортировки данных (т.н. [[Сортирующие сети]]), время работы которых в лучшем случае $O(\log n)$.
=== Время работы ===
Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее. Лучшее время - — минимальное время работы алгоритма на каком-либо наборе, обычно этим набором является тривиальный $\big[ 1 \ldots n \big] $. Худшее время - — наибольшее время.
У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.
=== Стабильность ===
''Стабильной сортировкой'' называется сортировка, не меняющая порядка объектов с одинаковыми ключами. Ключ — поле элемента, по которому мы производим сортировку.
=== Количество обменов ===
|$O(n + k)$
|$O(k)$
|$O(n + k)$
|Да
|$O(n + k)$
|Сортировка объектовцелых чисел, ключи которых входят входящих в заранее известный какой-то небольшой диапазон целых чисел. Создаем массив длины диапазона $k$ - длина диапазона, каждый элемент которого будет показывать, сколько исходных элементов равны данному. Бежим по массиву и считаем количество вхождений каждого числа.
|- align = "center"
|[[Сортировка Хэна (или Хана?)|Сортировка Хэна <br>(Han's Sort)]]
