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

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

Вычислительная сложность алгоритма O(n²).

Самая простая реализация на Java:

Достоинства:

  • Прост в реализации.
  • Подходит для связанных списков.

Недостатки

  • Нужна ещё память, равная по размеру исходному массиву.

Смотрите также интересный сайт, который визуализирует работу алгоритмов сортировки.

 

Внимание! Не следует писать алгоритмы сортировки самостоятельно для реальных приложений. Нужно использовать готовые алгоритмы для коллекций и методы из java.util.Arrays.

Вас также может заинтересовать сортировка слиянием и быстрая сортировка.

Один комментарий к “Алгоритм сортировки вставками”

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

    Сложность квадратична лишь в худшем случае. В лучшем — линейна.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *