Алгоритм сортировки вставками в Java: понятный пример и пошаговое руководство

Что такое алгоритм сортировки вставками?

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

В худшем и среднем случае сложность составляет O(n²), но на уже отсортированных данных работает за линейное время O(n). Это устойчивая, in-place сортировка, требующая только постоянное дополнительное пространство.

Процесс работы алгоритма

Наглядное представление работы сортировки вставками:

Процесс сортировки вставками

Пример программы на Java для сортировки массива методом вставок

package com.guru99;

public class InsertionSortExample {
    public static void main(String[] args) {
        int[] myArray = {860, 8, 200, 9};
        System.out.println("До сортировки вставками");
        printArray(myArray);
        insertionSort(myArray); // сортировка массива
        System.out.println("После сортировки вставками");
        printArray(myArray);
    }

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            System.out.println("Проход сортировки № " + i);
            int key = arr[i];
            int j = i - 1;
            while ((j > -1) && (arr[j] > key)) {
                System.out.println("Сравнение " + key + " и " + arr[j]);
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
            System.out.println("Обмен элементов: новый массив после обмена");
            printArray(arr);
        }
    }

    static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

Результат выполнения кода:

До сортировки вставками
860 8 200 9
Проход сортировки № 1
Сравнение 8 и 860
Обмен элементов: новый массив после обмена
8 860 200 9
Проход сортировки № 2
Сравнение 200 и 860
Обмен элементов: новый массив после обмена
8 200 860 9
Проход сортировки № 3
Сравнение 9 и 860
Сравнение 9 и 200
Обмен элементов: новый массив после обмена
8 9 200 860
После сортировки вставками
8 9 200 860