Сам алгоритм заключается в том, что элементы исходного массива просматриваются по одному, и каждый новый элемент вставляется в подходящее ему место среди ранее упорядоченных элементов. Место для вставки может выбираться, например, с помощью бинарного поиска, чтобы не приходилось просматривать все уже вставленные ранее элементы.
Вычислительная сложность алгоритма O(n²).
Самая простая реализация на Java:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
import java.util.Arrays; public class Main { public static void main(String[] args) { int[] array1 = { 5, 89, 5, -4, 0, 56, 3, 2, 6, -9 }; int[] result = insertsort(array1); System.out.println(Arrays.toString(result)); } public static int[] insertsort(int[] sourceArray) { int[] destinationArray = new int[sourceArray.length]; int destinationSize = 0; for (int n = 0; n < sourceArray.length; n++) { // Ищем место для вставки // Мы просто просматриваем все элементы, но при желании можно // использовать бинарный поиск. int insertIndex = 0; if (destinationSize > 0) { while (insertIndex < destinationSize && destinationArray[insertIndex] < sourceArray[n]) { insertIndex++; } } // Вставка for (int m = destinationSize - 1; m >= insertIndex; m--) { destinationArray[m + 1] = destinationArray[m]; } destinationArray[insertIndex] = sourceArray[n]; destinationSize++; } return destinationArray; } } |
Достоинства:
- Прост в реализации.
- Подходит для связанных списков.
Недостатки
- Нужна ещё память, равная по размеру исходному массиву.
Смотрите также интересный сайт, который визуализирует работу алгоритмов сортировки.
Внимание! Не следует писать алгоритмы сортировки самостоятельно для реальных приложений. Нужно использовать готовые алгоритмы для коллекций и методы из java.util.Arrays.
Вас также может заинтересовать сортировка слиянием и быстрая сортировка.
Небольшое замечание: дополнительный массив не нужен, сортировка происходит прямо в исходном. Нужна память только под 1 элемент — тот, для которого ищется место. Все элементы между местом изъятия и место вставки сдвигаются вправо на 1 позицию.
Сложность квадратична лишь в худшем случае. В лучшем — линейна.