SelectionSort и InsertionSort

Question

Я должен ответить на следующий вопрос: Не могли бы вы придумать сценарий, в котором SelectionSort лучше (с точки зрения разработки результата), чем InsertionSort.

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

Answer 1

InsertionSort имеет Ο(n^2) свопы в худшем случае, но SelectionSort равен Θ(n).Так что, если записи значительно дороже, чем чтение, SelectionSort лучше подходит.

Answer 2

Когда входной массив "близок к сортировке", сортировка выбора имеет лучшую производительность, чем сортировка вставкой.Также следует помнить о двух вещах: сортировка выбора требует только Θ (n) подстановок против Ο (n2) (в случае сортировки вставкой);Сортировка выбора имеет устойчивую реализацию, сортировка вставок не имеет.