Это три простых O(n²) сортировки сравнением. Они медленны на больших входных данных, но легки для понимания и полезны для обучения механике сортировки.
Это три простых O(n²) сортировки сравнением. Они медленны на больших входных данных, но легки для понимания и полезны для обучения механике сортировки.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # element to place
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift bigger elements right
j -= 1
arr[j + 1] = key # drop key into the gap
return arr
insertion_sort([5, 2, 4, 1]) # -> [1, 2, 4, 5]
| Сортировка | Лучший случай | Худший случай | Стабильность | На месте |
|---|---|---|---|---|
| Пузырьком | O(n) | O(n²) | Да | Да |
| Выбором | O(n²) | O(n²) | Нет | Да |
| Вставками | O(n) | O(n²) | Да | Да |
Сортировка вставками действительно быстра для маленьких или почти отсортированных массивов и используется в гибридных сортировках. Избегайте все три на больших неотсортированных данных — вместо этого используйте сортировки O(n log n).
Эти сортировки создают интуицию для инвариантов, обменов и стабильности перед тем, как вы перейдете к продвинутым алгоритмам.
Сортировка вставками в особенности появляется внутри промышленных сортировок (как Timsort) для крошечных подмассивов.
Понимание того, почему они O(n²), делает переход к сортировкам O(n log n) содержательным.
Библиотека вопросов для IT-собеседований с подробными ответами — от Junior до Senior.
Поддержать