Алгоритм сортировки вставками

public class InsertionSorter {
    public static void sort(int[] arr) {
        for (int k = 1; k < arr.length; k++) {
            int newElement = arr[k];
            int location = k - 1;
            while (location >= 0 && arr[location] > newElement) {
                arr[location + 1] = arr[location];
                location--;
            }
            arr[location + 1] = newElement;
        }
    }
}

На кожному кроці алгоритму ми вибираємо один з елементів вхідних даних і вставляємо його на потрібну позицію у вже відсортованому списку до тих пір, доки набір вхідних даних не буде вичерпано. Метод вибору чергового елементу з початкового масиву довільний; може використовуватися практично будь-який алгоритм вибору. Зазвичай (і з метою отримання стійкого алгоритму сортування), елементи вставляються за порядком їх появи у вхідному масиві.


public class InsertionSorter {
    public static void sort(int[] arr) {
         for (int k = 1; k < arr.length; k++) {
            int newElement = arr[k];

           for(int j = k; j>0; j--){
               int temp = arr[j-1];
               if(arr[j-1] > arr[j]){
                   arr[j-1]=arr[j];
                   arr[j]=temp;
               }
           }
        }
    }
}