Стабильная сортировка - это такая, которая сохраняет исходный порядок входного набора, где [нестабильный] алгоритм не различает два или более элементов.
Алгоритм сортировки считается стабильным, если два объекта с одинаковыми ключами появляются в отсортированном выводе в том же порядке, что и во входном массиве для сортировки.
Дополнительная информация: «Стабильный» алгоритм сортировки сохраняет элементы в одном и том же ключе сортировки по порядку. Например, у нас есть список слов из 5 букв:
peach straw apple spork
Стабильная сортировка, которая сортирует каждое слово по первой букве, приводит к следующему:
apple peach straw spork
В нестабильной сортировке straw
или spork
можно менять местами, но в стабильной сортировке они остаются в тех же относительных положениях.
Некоторые стабильные алгоритмы сортировки:
- Вставка сортировки
- Сортировка слиянием
- Пузырьковая сортировка
- Тим Сорт
- Подсчет сортировки
Примеры нестабильных алгоритмов сортировки:
- Сортировка кучи
- Выбор Сортировка
- Сортировка оболочки
- Быстрая сортировка
Заинтересованы в том, что вы здесь видите? Посмотрите эту классную визуализацию различных алгоритмов сортировки.