Что не так с моей логикой в ​​сортировке вставок Java?

Question

У меня был вопрос на тесте - я ошибся, но не знаю почему?

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

5 9 17 12 2 14

Как это будет выглядеть после третьего прохода цикла for?

17 9 5 12 2 14

17 12 9 5 2 14 - правильный ответ

17 12 9 5 14 2

17 14 12 9 5 2

9 5 17 12 2 14

В сортировке вставки я думал, что исходный массив не тронут; Я чувствовал, что на третьем проходе массив назначения будет неполным.

Как тест пришел к этому ответу?

Answer 1

Как правило, после n проходов сортировки вставкой первые n+1 элементы сортируются в правильном порядке, а остальные не затрагиваются. Как видно из альтернатив, правильный ответ - единственный, который удовлетворяет этому. На каждом шаге вставляется только относительно уже отсортированных номеров , поэтому на каждом шаге один дополнительный номер корректно сортируется.

Шаг 0 (оригинал, 5 предполагается отсортированным)

5 9 17 12 2 14

Шаг 1, берет 9 и помещает его в правильное место перед 5 (результат, 9 5 отсортировано)

9 5 17 12 2 14

Шаг 2, берет 17 и помещает его в правильное место перед 9 (результат 17 9 5 отсортировано)

17 9 5 12 2 14

Шаг 3, берет 12 и помещает его в правильное место после 17 и до 9 (результат 17 12 9 5 отсортирован)

17 12 9 5 2 14

Answer 2

Сортировка вставкой обычно выполняется на месте.После k итераций первые k + 1 элементы сортируются, поэтому вы ответили выше.