Алгоритм сортировки вставок в java

Question

Это мой алгоритм сортировки вставок. Но он всегда пропускает первый элемент в массиве.

Пример:

Вход: 5 8 4 9
Выход: 5 4 8 9

Вот код.

        import java.util.*;
        class InsertionSort {
        public void InsertAsc(int A [],int n)
        {
            for (int j=1; j<n; ++j){
                int key=A[j];
                int i=j-1;
                while(i>0 &&A[i]>key)
                {
                    A[i+1]=A[i];            
                    i=i-1;
                }
                A[i+1]=key;
            }
            System.out.println("The sorted numbers are"+Arrays.toString(A));
        }
    public static void main(String args[])
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter the numbers of number that you want to sort");
        int n=scan.nextInt();
        int A[]=new int[n];
        System.out.println("Enter the numbers that you want to sort");
        for(int i=0;i<n;i++)
        {
            A[i]=scan.nextInt();
        }

        System.out.println("The numbers are"+Arrays.toString(A));
        InsertionSort ob = new InsertionSort();
        ob.InsertAsc(A,n);
    }
}

Спасибо!

Answer 1

Обратите пристальное внимание на эту строку, пока (i> 0 && A [i]> key) вашей переменной мне нужно go для индекса 0, а в вашем случае это не так i> = 0 исправляет это.

Также я надеюсь, что вы можете представить себе, как работает алгоритм -

1. Вы go с индексом 1 до n-1 в вашем массиве с переменной j
   • Вы сохраняете элемент по индексу j в ключевой переменной, чтобы не потерять значение
   • Вы проверяете индексы от 0 до j-1 с вашей переменной i и продолжаете двигаться элементы больше, чем ключ, на шаг впереди
   • Таким образом, вы останавливаетесь на индексе i, содержащем элемент, меньший или равный ключу, или останавливаетесь на -1, если все элементы от 0 до i-1 больше, чем ключ
   • Наконец, вы помещаете свой ключевой элемент в индекс i + 1

Answer 2

    import java.util.*;
    class InsertionSort {
    public void InsertAsc(int A [],int n)
    {
        for (int j=1; j<n; ++j){
            int key=A[j];
            int i=j-1;
            while(i>-1 &&A[i]>key)
            {
                A[i+1]=A[i];

                i=i-1;
            }
            A[i+1]=key;
        }
        System.out.println("The sorted numbers are"+Arrays.toString(A));
    }
public static void main(String args[])
{

    Scanner scan = new Scanner(System.in);
    System.out.println("Enter the numbers of number that you want to sort");
    int n=scan.nextInt();
    int A[]=new int[n];
    System.out.println("Enter the numbers that you want to sort");
    for(int i=0;i<n;i++)
    {
        A[i]=scan.nextInt();

    }

    System.out.println("The numbers are"+Arrays.toString(A));


    InsertionSort ob = new InsertionSort();
    ob.InsertAsc(A,n);


}
}```