Временная сложность
Лучший: O(n)
Средний: O(n²)
Худший: O(n²)
Сортировка вставками формирует отсортированный массив по одному элементу за раз. Каждый элемент выбирается и вставляется на правильную позицию в уже отсортированной части массива.
Как работает:
1. Начинает со второго элемента (первый элемент уже считается отсортированным)
2. Выбирает текущий элемент в качестве "ключа"
3. Сравнивает ключ с элементами отсортированной части
4. Сдвигает большие элементы вправо
5. Вставляет ключ на правильную позицию
Временная сложность:
Лучшая: O(n) — массив уже отсортирован
Средняя: O(n²)
Худшая: O(n²) — массив отсортирован в обратном порядке
Пространственная сложность: O(1) — сортировка на месте
Свойства:
- Стабильная сортировка
- Адаптивная (эффективна для почти отсортированных данных)
- Сортировка на месте
- Онлайн-алгоритм (может сортировать данные по мере их поступления)
Отлично подходит для небольших наборов данных или почти отсортированных массивов. Часто используется как базовый алгоритм в гибридных алгоритмах сортировки, таких как Timsort.
Похожие алгоритмы
Частые вопросы
- Что такое Сортировка вставками (Insertion Sort)?
- Сортировка вставками формирует отсортированный массив по одному элементу за раз. Каждый элемент выбирается и вставляется на правильную позицию в уже отсортированной части массива.
- Какова сложность Сортировка вставками (Insertion Sort)?
- Время (среднее): O(n²) · Память: O(1)
- Для кого предназначена визуализация Сортировка вставками (Insertion Sort)?
- Визуализация Сортировка вставками (Insertion Sort) рассчитана на начальный уровень в категории «Сортировка». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Сортировка вставками (Insertion Sort)?
- В той же категории (Сортировка) вы можете изучить: Bubble Sort, Selection Sort, Quick Sort. Каждый из них имеет интерактивную визуализацию.