Где применяется
1. Задача
Сортировка слиянием дала время O(n log n). Она режет список пополам вслепую. Основную работу она делает потом, когда сливает половины. К той же скорости ведёт и другой путь: основную работу можно сделать до деления.
Выбери один элемент и назови его опорным (по-английски pivot). Остальные раздели на две группы: числа меньше опорного и числа не меньше опорного. Теперь опорный стоит на своём окончательном месте: слева от него всё меньше, справа всё равно ему или больше. Двигать его больше не придётся.
В этом одном действии вся идея. Сделай его, а потом сделай то же самое с каждой группой.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- сортировка массива реального размера (тысячи+)
- нужна гарантированная или ожидаемая O(n log n)
- сортировка как подготовительный шаг перед другим алгоритмом (два указателя, жадный, сканирующая прямая)
- нужна стабильность (сортировка слиянием) или сортировка на месте (быстрая сортировка)
- просто «отсортируй это» без намёка на малое n или особые ключи
Похоже, но не то
- Элементарные сортировки (выбором, пузырьком, вставками) (Elementary sorts (selection, bubble, insertion))
Те ничего не делят и стоят n в квадрате. Именно деление и покупает log n.
- Сортировка без сравнений (подсчётом / поразрядная) (Non-comparison sort (counting / radix))
Подсчёт и разряды обгоняют n log n, читая цифры. Им нужны ключи в узком диапазоне.
- Бинарная куча / очередь с приоритетом (Binary heap / priority queue)
Пирамидальная сортировка тоже n log n и без буфера. На практике она медленнее на реальных данных.
- Рекурсия (Recursion)
Рекурсия это механизм, а не сам приём. Главное здесь, где проходит разрез.
n до 1e6 даёт O(n log n). Merge требует O(n) дополнительной памяти, quick требует O(log n).
На LeetCode
Задачи, где массив делят вокруг опорного значения или ищут k-й по величине элемент без полной сортировки. Одно разбиение ставит опорный элемент на его окончательное место.
Разбиение из урока с отдельной группой для значений, равных опорному, и каждая группа сохраняет исходный порядок.
Одно разбиение, где вместо «меньше опорного» проверка «чётное».
Делай разбиение и продолжай только в той стороне, где лежит позиция k, так работает quickselect.
Бери случайный опорный элемент и отдельную группу для равных значений, потому что опорный элемент с конца слишком медленный на тестах с повторами.