Будет ли эта реализация сортировки учитывать сортировку вставкой?

Question

Эта реализация вставки считается правильной? Это немного отличается от некоторых других примеров, которые я видел.

public static int[] insertionSort(int[] numbers) {
    for (int i = 1; i < numbers.length; i++) {
        int index = i;
        for (int j = i-1; j >= 0 ; j--) {
            if (numbers[index] < numbers[j]) {
                int temp = numbers[index];
                numbers[index] = numbers[j];
                numbers[j] = temp;
                index--;
            }
        }

    }


    return numbers; 

}

Answer 1

Ваш лог c правильный, он должен работать и в принципе это сортировка вставкой, вы правы. Тем не менее, ваш алгоритм будет выполнять ненужные итерации в текущей реализации.

Внутренний l oop будет go через все значения, которые l ie оставил для i, даже если мы уже нашли место вставить. В результате ваше значение index будет указывать на правильное место, но l oop будет go дальше, но условие if не будет выполнено до следующего значения i.

Чтобы исправить это, вы можете просто добавить следующее:

else {
  break;
}

Это должно закончиться sh внутренним l oop и go к следующему значению внешнего l oop. Однако было бы еще лучше заменить внутренний l oop на while, чтобы сделать код более читабельным.

Что касается сложности, ваш текущий код будет работать со сложностью O (n ^ 2) даже для отсортированного массива. С таким улучшением он все равно будет работать в среднем на O (n ^ 2), но в лучшем случае он будет улучшен до O (n).