Кратко — на примере quicksort объясню худшее и среднее время, влияние выбора опорного элемента и практические улучшения для стабильной производительности.
1) Худший случай
- Случай: опорный элемент всегда оказывается экстремальным (например, всегда первый элемент при уже упорядоченном массиве).
- Рекуррентное соотношение: $T(n)=T(n-1)+cn$ (разбиение за $\Theta (n)$, одна подзадача размера $n-1$).
- Решение: $T(n)=\Theta (n^2)$. Память (глубина стека) в худшем случае: $\Theta (n)$.
2) Среднее (ожидаемое) время
- При равновероятном выборe опорного элемента (или при случайной перестановке входа) ожидаемый баланс разбиений даёт рекуррент
$E[T(n)]=\frac{1}{n}\sum _{k=0}^{n-1}(E[T(k)]+E[T(n-1-k)]+cn)$.
- Решение даёт $E[T(n)]=\Theta (n\log n)$. Для числа сравнений часто приводят асимптотическую оценку порядка $\approx 2n\ln n$ (плюс $O(n)$). Память в среднем: $O(\log n)$.
3) Влияние выбора опорного элемента
- Плохой выбор (например, всегда первый/последний) делает алгоритм чувствительным к уже/обратно упорядоченным входам → легко получить $\Theta (n^2)$.
- Случайный выбор опорного элемента или предварительная случайная перестановка входа переводит поведение в ожидаемое $\Theta (n\log n)$ и уменьшает вероятность худшего случая.
- Примитивная эвристика «median-of-three» (медиана из первого, среднего и последнего) часто улучшает разбиения на частично отсортированных данных.
- Наличие множества равных ключей сильно ухудшает работу обычного двухстороннего partition; трёхчастное разбиение (Dutch national flag) решает это.
4) Практические модификации для стабилизации производительности
- Предварительная случайная перестановка (shuffle) массива: гарантирует, что вход не будет специально подобран против детерминированного pivot-правила.
- Рандомизация pivot: выбирать опорный случайно при каждом вызове — простая защита от антипримеров.
- Median-of-three или median-of-k: брать медиану небольшой выборки (обычно $k=3$ или $k=5$) — лучшее практическое среднее поведение.
- Трёхсекторное partition (включая равные элементы): при множестве равных ключей даёт время близкое к $\Theta (n)$ в экстремуме.
- Переход на insertion sort для мелких подмассивов (например, размер $\le 16$–$32$) — уменьшает константы и ускоряет на малых n.
- Introsort: начать как quicksort, но если глубина рекурсии превышает порог (обычно $2{\log }_{2}n$), переключиться на heapsort — даёт практическую скорость quicksort с гарантией худшего случая $\Theta (n\log n)$.
- Выбор опорного через детерминированный selection (median-of-medians) даёт теоретически гарантированное хорошее разбиение и худший случай $\Theta (n\log n)$, но с большими константами — редко нужен в практике.
- Устранение хвостовой рекурсии и контроль стека: всегда рекурсировать в меньшей части и делать итеративно большую часть — уменьшает максимальную глубину стека до $O(\log n)$ при сбалансированных разбиениях.
5) Рекомендация для реальных данных (коротко)
- Использовать quicksort с рандомизацией или предварительным shuffle, median-of-three, трёхсекторным partition и переходом на insertion sort для мелких частей; добавить introsort как страховку против враждебных входов. Это даёт хорошую практическую производительность и защиту от худших случаев.
Если нужно, могу привести псевдокод для трёхсекторного partition, median-of-three или пример настройки порога для insertion sort.