Пример реализации на Kotlin: fun insertionsort(items:MutableList): List {
if (items.isEmpty() || items.size < 2){
return items
}
for (count in 1..items.count() - 1) {
val item = items[count]
var i = count
while (i > 0 && item < items[i - 1]) {
items[i] = items[i - 1]
i -= 1
}
items[i] = item
}
return items
}
Сложность
Лучшее
Среднее
Худшее
Время
O(n)
O(n2)
O(n2)
Память
O(1)
Сортировка Шелла / Shell sort Сортировка Шелла - усовершенствованная разновидность сортировки вставками.
Сначала сравниваются и сортируются между собой значения, стоящие друг от друга на некотором расстоянии - d. После этого расстояние d уменьшается и процедура повторяется до тех пор, пока значение d не станет минимальным, т.е. d = 1. Это означает, что сортировка достигла последнего шага. А на последнем шага элементы сортируются обычной сортировкой вставками.
Первоначально было предложено расчитывать расстояние между сравниваемыми элементами следующим образом:
первая итерация - d1 = N/2, где N - размер массива;
