1. Задача
Ты уже написал несколько сортировок. Пузырьковая, выбором и вставками работают за O(n2). Слиянием и быстрая работают за O(n log n), быстрая в среднем. Для целого семейства сортировок сортировка за O(n) на любом списке невозможна, и у этого есть точная причина. Все сортировки, которые ты видел, узнают о порядке одним способом. Они сравнивают два элемента, спрашивают «этот меньше?» и по ответу «да» или «нет» решают, что делать дальше. Других сведений о порядке у них нет. Этот урок показывает, почему такой способ ограничивает скорость, и вычисляет этот предел.
В продакшен этот код не пойдёт. Он нужен, чтобы понять, когда пора перестать ускорять сортировку сравнением и взять сортировку другого рода.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- ключи это целые числа в небольшом известном диапазоне
- сортировка возрастов, оценок или ограниченных счётчиков
- нужна O(n), а сравнения стали узким местом
- сортировка по разрядам или ключу фиксированной ширины
- n большое, но диапазон значений намного меньше n
Похоже, но не то
- Быстрая сортировка (merge / quick) (Fast sort (merge / quick))
Никакая сортировка сравнением не быстрее n log n. Чтение ключа обходит этот предел целиком.
- Хеш-множество / словарь (Hash set / map)
Словарь тоже считает значения, но порядка не хранит. Сортировка подсчётом делает значение индексом.
- Сортировка с пользовательским компаратором (Sort with a custom comparator)
Компаратор описывает порядок между двумя элементами. Подсчёт вообще не смотрит на пары.
- Элементарные сортировки (выбором, пузырьком, вставками) (Elementary sorts (selection, bubble, insertion))
Те сравнивают соседей и стоят n в квадрате. Подсчёт линеен, если диапазон позволяет.
n значений с ключами меньше k дают O(n + k). Поразрядная стоит O(d умножить на n) при d разрядах.
На LeetCode
Ни одна задача на LeetCode не просит доказать эту границу. Она подсказывает, когда хватит искать сортировку сравнением побыстрее, и если задача требует O(n) на числах, как Maximum Gap, нужна сортировка подсчётом или поразрядная из уроков 39 и 40.