Algorytm sortowania wsadowego nie działa zgodnie z oczekiwaniami - java, sortowanie, wstawianie-sortowanie

Mój kod sortowania wtrącania to:

class insertionsort
{
public static void main(String s[])
{
int []A={12,5,8,87,55,4};
int []R=sort(A);
for(int i=0;i<A.length;i++)
{
System.out.println(R[i]);
}
}
static int[] sort(int A[])
{
int key,i,j;
for(j=1;j<A.length;j++)
{
key=A[j];
i=j-1;
while(i>=0 && A[j]<A[i])
{
A[j]=A[i];
i--;
}
A[i+1]=key;
}
return A;
}
}

Ale wynik nie jest poprawny. Jednak jeśli zastąpię A[j] z key w stanie pętli while i A[j] z A[i+1] w pętli while, kod generuje poprawny wynik. Czy jest jakaś różnica między A[j] i key i A[j] i A[i+1]?

Odpowiedzi:

Prawidłowy kod:

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

Zauważ, że nie musisz niczego zwracać, ponieważ sama metoda zmienia tablicę wejściową.

P: Czy jest jakaś różnica w A [j] i kluczach lub A [j] i A [i + 1]?

Oczywiście. Cały punkt algorytmu sortowania wstawiania polega na tym, że wymienia on bieżący element ze wszystkimi elementami po lewej stronie, które są większe od niego. Wyobraź sobie, że przestawiasz karty w ręce. W oryginalnej wersji j jest ustalony w wewnętrznej pętli, a przegrupowanie się nie dzieje.