Где применяется
1. Задача
У тебя список чисел в случайном порядке, а нужен он от меньшего к большему. Цель та же, что в двух прошлых уроках, а способ другой.
Возьми таблицу лидеров, куда результаты приходят по одному. На доске уже стоят 2, 5 и 8, по порядку. Приходит 3. Сортировать всю доску заново не нужно: достаточно вставить 3 между 2 и 5. Доска снова упорядочена и стала на одно число длиннее.
Так и работает этот способ. Он берёт числа по одному и вставляет каждое на своё место среди уже упорядоченных.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- n маленькое (десятки или пара сотен)
- массив уже почти отсортирован
- сортировка на месте с O(1) дополнительной памяти
- учебный/собеседовательный вопрос о механике сортировки
- важна стабильность, а простота приемлема
Похоже, но не то
- Быстрая сортировка (merge / quick) (Fast sort (merge / quick))
Merge и quick делят массив и стоят n log n. Эти три ничего не делят.
- Сортировка без сравнений (подсчётом / поразрядная) (Non-comparison sort (counting / radix))
Сортировка подсчётом читает значения, а не сравнивает их. Для этого нужен небольшой диапазон ключей.
- Сортировка с пользовательским компаратором (Sort with a custom comparator)
Та страница про то, какой порядок вам нужен. Эта про то, как порядок получается.
- Бинарная куча / очередь с приоритетом (Binary heap / priority queue)
Сортировка выбором каждый раунд ищет минимум перебором. Куча отдаёт его за log n.
n примерно до 5000 нормально при O(n в квадрате). На почти отсортированных данных вставки дают O(n).
На LeetCode
Задачи, где значения приходят по одному и список должен оставаться отсортированным, или в отсортированный список нужно добавить новые значения. Сдвигай большие значения вправо и ставь новое в освободившуюся ячейку.
Держи оценки отсортированными, вставляя каждую новую на её место, и читай k-ю по величине.
В nums1 есть место в конце, поэтому вставляй каждое значение из nums2, сдвигая большие вправо.
Сортировка вставками на месте проходит на 300 значениях и сохраняет порядок одинаковых цветов.