Быстрая, слиянием, пирамидальная — три способа упорядочить данные за O(n log n) с разными свойствами по памяти, устойчивости и худшему случаю.
Ключевые тезисы
- Нижняя граница сравнениями — O(n log n); обойти её можно только не сравнивая (поразрядная).
- быстра в среднем, но её худший случай квадратичен — отсюда случайный выбор опорного.
- Устойчивость важнее, чем кажется: она позволяет сортировать по нескольким ключам последовательно.
Видеолекции
Записи университетских курсов, где эта тема звучит. Где у записи есть тайм-коды, ссылка открывает её с нужной секунды; где их не проставили — с начала.
Связанные темы
Структуры данных
Hash Tables85%
Хеш-таблицы · Алгоритмы и структуры данныхДоступ по ключу за константу в среднем. Основа словарей и множеств — и структура, на которой держится большая часть повседневного кода.
Arrays, Lists, Stacks and Queues85%
Массивы, списки, стеки и очереди · Алгоритмы и структуры данныхЧетыре базовых способа хранить последовательность. Отличаются не тем, что умеют, а тем, что у них дёшево, а что дорого.
Trees and Heaps85%
Деревья и кучи · Алгоритмы и структуры данныхИерархические структуры, дающие логарифмические операции: двоичное дерево поиска для упорядоченных запросов, куча — для быстрого минимума.
Order Statistics85%
Порядковые статистики · Алгоритмы и структуры данныхНайти k-й по величине элемент, не сортируя весь массив. Quickselect делает это в среднем за линию.
Caching85%
Кеширование · Системный дизайн ML-сервисовНе считать то, что уже посчитано: кеш предсказаний, признаков и эмбеддингов.
Тема встречается в тесте по направлениям — ошибки приведут обратно на эту страницу.
Глава «Алгоритмы и структуры данных» последний раз правилась . Нашли ошибку — напишите.