Почему выборочная сортировка нестабильна?

Question

Это может быть тривиально, но я не понимаю, почему реализация по умолчанию Выбор сортировки не стабильна?

На каждой итерации вы найдете минимальный элемент в оставшемся массиве. Найдя этот минимум, вы можете выбрать первый найденный минимум и обновлять его только тогда, когда элемент на самом деле меньше его. Таким образом, выбранный элемент на каждой итерации является первым минимумом, т. Е. Первым в предыдущем порядке сортировки. Поэтому, насколько я понимаю, текущая сортировка не уничтожит порядок, сгенерированный предыдущей сортировкой на равных элементах.

Чего мне не хватает?

Answer 1

Небольшой пример:

Пусть b = B в

, , , (с После одного цикла последовательность сортируется, но порядок B и b изменился:

, , ,

Но вы можетеоднако реализуйте Селекции Сортировка стабильно, если вместо переключения ввести минимальное значение.Но для того, чтобы это было эффективным, у вас должна быть структура данных, которая поддерживает вставку при низких затратах, иначе вы получите квадратичную сложность.

Answer 2

Проблема заключается в том, что выборочная сортировка заменяет элементы из передней части массива в точку, освобожденную минимальным элементом, что может испортить отсортированный порядок. Например, предположим, что я сортирую

(4, 0), (4, 1), (1, 0)

Выбор сортировки сначала меняет (1, 0) на передний план:

(1, 0), (4, 1), (4, 0)

И теперь (4, 0) и (4, 1) вышли из строя с того места, с которого они начали сортировку. Выполнение этого до конца оставляет элементы в этом порядке, а четверки выходят из строя.

Надеюсь, это поможет!

Answer 3

Стабильное средство не рассчитывает дальше, если элементы уже отсортированы, но оно рассчитывает до конца, следовательно, оно не стабильно