Сортировка вставками

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

Сортировка вставками — один из самых простых методов сортировки. Её основная идея заключается во вставке записи в уже отсортированную упорядоченную таблицу, в результате чего образуется новая упорядоченная таблица с числом записей, увеличенным на 1.

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

Как это работает

Основная идея сортировки вставками —«построение упорядоченной последовательности»Она логически делит массив (или список), который нужно отсортировать, на две части:

  1. Отсортированная частьИзначально первый элемент массива обычно считается упорядоченной последовательностью сам по себе.
  2. Неотсортированная частьОт второго элемента до последнего элемента.

Алгоритм будетПовторно вставлять первый элемент неотсортированной части в правильную позицию отсортированной части.Пока неотсортированная часть не станет пустой, весь массив становится отсортированным.

Применимость

Средняя временная сложность сортировки вставками также равнаO(n^2), а пространственная сложность имеет постоянный порядокO(1)Конкретная временная сложность также связана с упорядоченностью массива.

В сортировке вставками, когда массив, который нужно отсортировать, уже упорядочен, это оптимальный случай. Нужно только сравнить текущее число с предыдущим числом, и общее количество сравнений, необходимых в этом случае, равноN-1раз, а временная сложность равнаO(N)Худший случай — когда массив, который нужно отсортировать, находится в обратном порядке. В этом случае количество сравнений наибольшее. Худший случай —O(n^2)。

Схема процесса

Предположим, что предыдущиеn-1(гдеn>=2) чисел уже отсортированы. Теперь вставимnчисло в ранее отсортированную последовательность, затем найдём его подходящую позицию, чтобы последовательность после вставки n-го числа также была отсортирована.

Процесс вставки всех элементов таким способом до тех пор, пока вся последовательность не будет отсортирована, называется сортировкой вставками.

Весь процесс сортировки вставками по возрастанию показан на рисунке:

Первый проход:Начиная с 6 на второй позиции, оно меньше стоящей впереди 7, поэтому нужно поменять их местами.

Второй проход:9 на третьей позиции больше 7 на предыдущей позиции, поэтому обмен не нужен.

Третий проход:3 на четвёртой позиции меньше 9 на предыдущей позиции, поэтому меняем местами и сравниваем вперёд по одному.

Четвёртый проход:1 на пятой позиции меньше 9 на предыдущей позиции, меняем местами, затем сравниваем вперёд по одному.

......

Таким образом, сравниваем по одному до последнего элемента.

Пример кода на Java

Загрузка пакета исходного кода:Скачать

Фрагмент кода:

Код файла InsertionSort.java:

package example;

/**
* Сортировка вставками
 */
public class InsertionSort {
    // Основной код --- начало
    public static void sort(Comparable[] arr){

        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // Найти подходящую позицию вставки для элемента arr[i]
           for( int j = i ; j > 0 ; j -- )
                if( arr[j].compareTo( arr[j-1] ) < 0 )
                    swap( arr, j , j-1 );
                else
                    break;
        }
    }
    // Основной код --- конец
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {

        int N = 20000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        InsertionSort.sort(arr);
        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }

}

Реализация алгоритма и анализ кода

После понимания принципа, давайте посмотрим на конкретную реализацию кода. Здесь мы предоставляем версии на двух распространённых языках: Python и Java.

Реализация на Python

Пример

def insertion_sort(arr):
    """
Реализация алгоритма сортировки вставками (по возрастанию)
:param arr: список для сортировки
:return: Отсортированный список (изменён на месте, также возвращён)
    """
    # Пройти от второго элемента до последнего (индекс от 1 до n-1)
    for i in range(1, len(arr)):
        current_value = arr[i]  # Текущий элемент для вставки, сначала "взят в руку"
        j = i - 1               # j указывает на последний элемент отсортированной последовательности
       
        # Внутренний цикл: найти позицию вставки для current_value в отсортированной части arr[0..i-1]
        # Условие 1: j >= 0 гарантирует отсутствие выхода за границы перед началом списка
        # Условие 2: arr[j] > current_value означает, что текущий сравниваемый элемент больше "удерживаемого" и его нужно сдвинуть назад
        while j >= 0 and arr[j] > current_value:
            arr[j + 1] = arr[j]  # Переместить больший элемент на одну позицию назад, чтобы освободить место
            j -= 1               # Продолжить сравнение следующего элемента слева
       
        # Цикл завершается, значит позиция вставки (j+1) найдена
        # На этом этапе arr[j] <= current_value или j == -1
        arr[j + 1] = current_value  # Вставить "удерживаемый" элемент в правильную позицию
   
    return arr


# Тестовый код
if __name__ == "__main__":
    # Тестовые данные
    test_data = [64, 34, 25, 12, 22, 11, 90]
    print("Перед сортировкой:", test_data)
   
    sorted_data = insertion_sort(test_data.copy())  # Сортировать, используя копию, чтобы исходные данные не изменились
    print("После сортировки:", sorted_data)
   
    # Ещё один тест: почти отсортированные данные
    nearly_sorted_data = [1, 3, 2, 4, 6, 5, 8, 7]
    print("\n"Почти отсортированные данные до сортировки:", nearly_sorted_data)
    print("Почти отсортированные данные после сортировки:", insertion_sort(nearly_sorted_data.copy()))

Реализация на Java

Пример

public class InsertionSort {
   
    public static void insertionSort(int[] arr) {
        # Пройти от второго элемента до последнего (индекс от 1 до n-1)
        for (int i = 1; i < arr.length; i++) {
            int currentValue = arr[i]; # Текущий элемент для вставки
            int j = i - 1;             # j указывает на последний элемент отсортированной последовательности
           
            # Внутренний цикл: найти позицию вставки и переместить элементы
            while (j >= 0 && arr[j] > currentValue) {
                arr[j + 1] = arr[j]; # Сдвинуть элемент вправо
                j--;
            }
           
            # Вставить текущий элемент в правильную позицию
            arr[j + 1] = currentValue;
        }
    }
   
    # Перегруженный метод, поддерживает сортировку части массива целых чисел
    public static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int currentValue = arr[i];
            int j = i - 1;
           
            while (j >= left && arr[j] > currentValue) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = currentValue;
        }
    }
   
    public static void main(String[] args) {
        # Тестовые данные
        int[] testData = {64, 34, 25, 12, 22, 11, 90};
        System.out.print("Перед сортировкой: ");
        printArray(testData);
       
        int[] dataToSort = testData.clone(); # Использовать копию
        insertionSort(dataToSort);
        System.out.print("После сортировки: ");
        printArray(dataToSort);
    }
   
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Анализ характеристик алгоритма

Понимание производительности и сценариев применения алгоритма имеет решающее значение. Характеристики сортировки вставками можно обобщить следующим образом:

Особенности Описание Объяснение
Временная сложность Средний и худший случаи: $O(n^2)$ Вложенные циклы необходимы для сравнения и перемещения элементов. Для n элементов в худшем случае (полностью обратном порядке) требуется около $\frac{n(n-1)}{2}$ сравнений и перемещений.
Лучший случай：$O(n)$ Когда входной массив уже в основном отсортирован, внутренний цикл редко выполняется или сразу завершается, и требуется всего n-1 сравнений.
Пространственная сложность $O(1)$ ДаСортировка на месте —алгоритм, требующий только дополнительного пространства постоянного уровня (такого какcurrent_value, jи других переменных).
Стабильность Устойчивая Когда два элемента равны, их относительный порядок после сортировки остаётся неизменным. Потому что алгоритм перемещает элементы только тогда, когда встречает значение,большее, чемтекущее.
Применимые сценарии 1. Небольшой объём данных
2. Данные в основном упорядочены
3. В качестве вспомогательной процедуры для продвинутых алгоритмов сортировки (таких как быстрая сортировка, сортировка слиянием)		 В этих случаях его логика и низкие постоянные накладные расходы могут сделать его работу лучше, чем более сложные алгоритмы $O(n \log n)$.

Вывод формулы временной сложности (худший случай)

В худшем случае (массив в полностью обратном порядке):

  • 1-й элемент (индекс 0) вставляется, сравнивается 0 раз.
  • Вставляется 2-й элемент (индекс 1), сравнивается 1 раз, перемещается 1 раз.
  • Вставляется 3-й элемент (индекс 2), сравнивается 2 раза, перемещается 2 раза.
  • ...
  • Вставляется n-й элемент (индекс n-1), сравнивается n-1 раз, перемещается n-1 раз.

Общее количество сравнений и перемещений равно: $0 + 1 + 2 + ... + (n-1) = \frac{n(n-1)}{2}$

Следовательно, временная сложность равна $O(n^2)$.

Больше примеров кода

Другие расширения