вставки не работает, как ожидалось

Question

Мой код для вставки сортировки:

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; 
    } 
} 

Но результат не является правильным. Однако, если я заменил A[j] на key во время цикла и A[j] с A[i+1] в цикле цикла, код генерирует правильный результат. Есть ли разница между A[j] и key и A[j] и A[i+1]?

Answer 1

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

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; 
     } 
    } 

Обратите внимание, что вы не должны ничего возвращать, так как метод сам изменяет массив ввода.

Q: Есть ли разница в A [J] и клавишу или A [J] и A [I + 1]?

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