Ошибка в сортировке вставки Java

Question

Я пытался закодировать сортировку вставкой в ​​Java с помощью псевдокода из книги. Выходные данные для этого кода должны быть числами в порядке возрастания, но по какой-то причине я получаю 10,4,5,6,7,8,9. Любая помощь с благодарностью! Спасибо!

public class InsertionSort {

    public int Array[] = {10,9,8,7,6,5,4};

    public static void main(String[] args) {
        InsertionSort obj1 = new InsertionSort();
    }

    public InsertionSort() {
        InsertionSortMethod();
        PrintArray();
    }

    public void InsertionSortMethod() {
        for(int j = 2; j < Array.length; j++) {
            int key = Array[j];
            int i = j - 1;
            while(i > 0 && Array[i] > key) {
                Array[i + 1] = Array[i];
                i = i - 1;
            }
            Array[i + 1] = key;
        }   
    }

    public void PrintArray() {
        for(int i = 0; i < Array.length; i++) {
            System.out.println(Array[i]);
        }
    }
}

Answer 1

попробуйте этот метод

 public int[] insertionSort(int[] list) {
            int i, j, key, temp;
            for (i = 1; i < list.length; i++) {
                key = list[i];
                j = i - 1;
                while (j >= 0 && key < list[j]) {
                    temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                    j--;
                }

            }
            return list;
        }

Answer 2

В третьей строке вашего кода, т.е.

InsertionSort obj1 = new InsertionSort();

Вы создаете объект класса InsertionSort, но в вашем коде он определен как функция. Я думаю, что это конструктор, вы должны упомянуть класс для большего удобства читателя.

Кроме того, вы начинаете свой цикл с 2 for(int j = 2; j < Array.length; j++) почему так? ваш один элемент пропустил, поэтому начните J с 1 :)

Answer 3

Спасибо за все ответы. Я также обнаружил, отслеживая алгоритм, что переключение второго знака «больше, чем» на знак «меньше» на 5-й строке алгоритма позволяет работать в порядке убывания. Это может быть опечатка в книге, которую я читаю. Еще раз спасибо!

Answer 4

Запустите цикл for с j = 1 следующим образом:

for(int j = 1; j < array.length; j++) {

и измените условие цикла while следующим образом:

while(i >= 0 && array[i] > key) {

Правильный рабочий код:

public class InsertionSort {

public int array[] = {10,9,8,7,6,5,4};

public static void main(String[] args) {
    InsertionSort obj = new InsertionSort();
    obj.insertionSortMethod();
    obj.printArray();
}


public void insertionSortMethod() {
    for(int j = 1; j < array.length; j++) {
        int key = array[j];
        int i = j - 1;
        while(i >= 0 && array[i] > key) {
            array[i + 1] = array[i];
            i = i - 1;
    }
        array[i + 1] = key;

    }   
}

public void printArray() {
    for(int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
}

}