Это может быть тривиально, но я не понимаю, почему стандартная реализация Selection Sort нестабильна?
На каждой итерации вы найдете минимальный элемент в оставшемся массиве. Найдя этот минимум, вы можете выбрать первый минимум, который вы найдете, и обновлять его только тогда, когда элемент на самом деле меньше его. Таким образом, выбранный элемент на каждой итерации является первым минимумом, то есть первым в предыдущем порядке сортировки. Итак, по моему мнению, текущий сорт не уничтожит порядок, созданный предыдущим типом, на равных элементах.
Что мне не хватает?
Небольшой пример:
Пусть b = B в
<B> , <b> , <a> , <C> (с < b < c)
После одного цикла последовательность сортируется, но порядок B и b изменился:
<a> , <b> , <B> , <c>
Но вы можете, однако, внедрить Selections Sort stable, если вместо переключения ввести минимальное значение. Но для того, чтобы быть эффективными, у вас должна быть структура данных, поддерживающая вставку с низкой стоимостью или в противном случае вы получите квадратичную сложность.
Проблема заключается в том, что сортировка сортировки сводит элементы из передней части массива в пятно, освобожденное минимальным элементом, что может испортить отсортированный порядок. Например, предположим, что я сортирую
(4, 0), (4, 1), (1, 0)
Сортировка сортировки сначала сворачивает (1, 0) вперед:
(1, 0), (4, 1), (4, 0)
И теперь (4, 0) и (4, 1) не соответствуют порядку, с которого они начали в сортировке. Выполнение этого до завершения оставляет элементы в этом порядке, а 4s выходят из строя.
Надеюсь, это поможет!
Стабильные средства не вычисляются дальше, если элементы уже отсортированы, но вычисляются до конца, следовательно, они нестабильны.