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

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

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

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

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

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

Недостатки

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

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

 

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

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


Поделиться:
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...

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

Ваш e-mail не будет опубликован.

*