Как я могу исправить алгоритмы сортировки и вставки сортировки

Question

Я написал алгоритмы сортировки и вставки, которые дают мне неправильные несортированные выходы. Вот мой код для выбора вида:

public class SelectionSort { 

    public static void main(String[] args) { 

     int[] arr = {23,43,45,3,54,55,23,12,22}; 

     int min; 
     int temp = 0; 

     for(int i = 0; i < arr.length-1; i++) 
     { 
      min = i; 
      for(int j = i+1; j<arr.length; j++) 
      { 
       if(arr[j] < arr[min]) 
       { 
        min = j; 

       } 
       temp = arr[j]; 
       arr[j] = arr[min]; 
       arr[min] = temp; 
      } 

     } 

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


    } 

} 

Выход: 45 55 54 43 23 23 22 12 3

Это не отсортирован, и я хочу, чтобы отсортировать в порядке возрастания.

Вот моя вставка сортировать:

public class Insertion { 

    public static void main(String[] args) { 

     int[] arr = {2,4,6,5,4,3,5,3}; 

     for(int i = 1; i < arr.length; i++) 
     { 
      int temp = arr[i]; 

      int j = i; 

      while(j > 0 && arr[j-1] > arr[j]) 
      { 
       arr[j] = arr[j-1]; 
       j = j-1; 
      } 
      arr[j] = temp; 
     } 

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

    } 
} 

Выход: 2 4 5 4 3 5 3 6

Answer 1

В вашем выборе рода, давайте сосредоточимся на этой части кода:

for(int i = 0; i < arr.length-1; i++) 
    { 
     min = i; 
     for(int j = i+1; j<arr.length; j++) 
     { 
      if(arr[j] < arr[min]) 
      { 
       min = j; 

      } 
      temp = arr[j]; // <--- 
      arr[j] = arr[min]; 
      arr[min] = temp; 
     } 
    } 

Идея высокого уровня, лежащая в основе выбора, состоит в том, чтобы найти наименьший элемент в диапазоне [i, n), а затем замените его элементом в позиции i. Обратите внимание, что с кодом, который вы здесь, вы постоянно меняете текущий индекс с индексом min, который не является свопом, который вы хотите сделать. В качестве подсказки сделайте не более одного свопа на итерацию внешнего контура и замените это подкачку между позицией i и позицией min. Если вы меняете раньше, вы получите неправильный ответ.

Для сортировки вставки существует более тонкая ошибка. Вот где ошибка:

while(j > 0 && arr[j-1] > arr[j]) 
{ 
    arr[j] = arr[j-1]; 
    j = j-1; 
} 
arr[j] = temp; 

Обратите внимание, что всякий раз, когда текущий элемент сравнивает меньше, чем элемент перед ним, вы перезаписать текущий элемент с элементом перед ним, затем уменьшает J. Однако вы не обновляете arr[j-1] с текущим элементом, поэтому в следующем сравнении вы сравниваете элемент, который раньше находился в позиции j-1, с элементом, который находится в позиции j-2, вместо сравнения текущего элемента с элементом в позиция j-2. Чтобы исправить это, обновите сравнение, которое всегда сравнивается с temp, а не arr[j]:

while(j > 0 && arr[j-1] > temp) 
{ 
    arr[j] = arr[j-1]; 
    j = j-1; 
} 
arr[j] = temp;