Вставка Сортировка не соответствует ожидаемому

Question

Неверный результат сортировки ввода. Когда я попытался вызвать метод insertionSort, возвращаемый массив не отсортирован

Правильное использование оператора break?

public int[] insertionSort(int [] arr){ 
    for(int i=1;i<arr.length;i++){ 
     for(int j=0;j<=i-1;){ 
      int temp; 
      if(arr[i] < arr[j]){ 
       temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; 
       break; 
      } 
      else j++; 
      } 
     } 
     return arr; 
} 

называемый метод с int [] array = {10,5,6,7,1,9,3,8}, но результат неверен:

Выход После сортировки: 1, 3, 7, 8, 5, 10, 6, 9, // вывод не сортируется, но она изменяется несколько

Answer 1

Вот код, который работает:

public static int[] insertionSort(int[] arr) { 
     for (int i = 1; i < arr.length; i++) { 
      int j = i; 
      while (j > 0 && arr[j] < arr[j - 1]) { 
       // Swap 
       int tmp = arr[j]; 
       arr[j] = arr[j - 1]; 
       arr[j - 1] = tmp; 

       j--; 
      } 
     } 
     return arr; 
    } 

Один из й e проблемы с вашим кодом в том, что вы положите элемент i-th в правильное положение, но, возможно, испортите положение элемента, который уже был в правильном положении.

Идея сортировки вставки заключается в том, чтобы вставить элемент i-th в правильное положение, что означает, что вы должны переместить все элементы вправо. Однако в вашем случае вы просто поменяете j-th элемент и i-th после нахождения правильной позиции.

Пример: 1 3 5 8 10 это текущее состояние массива Теперь вы пытаетесь вставить элемент 6 и вы обнаружите, что правильное положение 3, поэтому поменять их местами и результат: 1 3 5 6 10 8 который испортил позиция для номера 8.