algorithm
Сортировка
Поиск…
параметры
| параметр | Описание |
|---|---|
| стабильность | Алгоритм сортировки является стабильным, если он сохраняет относительный порядок равных элементов после сортировки. |
| На месте | Алгоритм сортировки на месте, если он сортирует, используя только O(1) вспомогательную память (не считая массив, который нужно сортировать). |
| Наилучшая сложность случая | Алгоритм сортировки имеет наилучшую временную сложность O(T(n)) если ее время работы не менее T(n) для всех возможных входов. |
| Средняя сложность случая | Алгоритм сортировки имеет среднюю временную сложность O(T(n)) если ее время работы, усредненное по всем возможным входам , равно T(n) . |
| Худшая сложность случая | Алгоритм сортировки имеет худшую временную сложность O(T(n)) если ее время работы не превышает T(n) . |
Стабильность при сортировке
Стабильность в сортировке означает, поддерживает ли алгоритм сортировки относительный порядок равных ключей исходного ввода в выходном результате.
Таким образом, алгоритм сортировки считается стабильным, если два объекта с равными ключами отображаются в том же порядке в отсортированном виде, что и во входном несортированном массиве.
Рассмотрим список пар:
(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)
Теперь мы отсортируем список, используя первый элемент каждой пары.
При стабильной сортировке этого списка будет выводиться следующий список:
(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)
Потому что (9, 3) появляется после (9, 7) в исходном списке.
Нестабильная сортировка выведет следующий список:
(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)
Нестабильная сортировка может генерировать тот же результат, что и стабильный, но не всегда.
Известные стабильные сорта:
- Сортировка слиянием
- Сортировка вставки
- Radix sort
- Тим сортировать
- Сортировка пузырьков
Известные неустойчивые сорта:
