Блог

Я только что написал следующий код, и я не уверен, правильная ли это реализация сортировки вставки в Java (для меня это выглядело слишком похоже на сортировку пузырьками, чтобы быть уверенным).

 public static void insertionsort (int[] arr){
    int temp;
    for (int i = 0; i<arr.length; i  ){
            for (int j = i 1; j>=0; j--){
            
             if (arr[j]<arr[j-1]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
                            
         }
        
    }
    
}
 

Когда я сравнил свои решения с решениями в Интернете, я заметил, что все они используют переменную для хранения arr [i] .
например:

 void sort(int arr[]) 
{ 
    int n = arr.length; 
    for (int i = 1; i < n;   i) { 
        int key = arr[i]; 
        int j = i - 1; 

        /* Move elements of arr[0..i-1], that are 
           greater than key, to one position ahead 
           of their current position */
        while (j >= 0 amp;amp; arr[j] > key) { 
            arr[j   1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j   1] = key; 
    } 
} 
 

Какова цель этой ключевой переменной? Разве это не немного избыточно?

Цель ключевой переменной — сохранить значение, которое будет вставлено в его отсортированную позицию после внутреннего цикла. Как кажется, теперь ваше решение недостаточно работает для сортировки вставки.