Ниже — компактный, но полный разбор быстрой сортировки с выбором опорного элемента «случайный», с анализом среднего и худшего времени, эффектом выбора опоры и повторяющихся ключей, а также практическими адаптациями для надёжной производительности.

1) Короткое описание алгоритма

Алгоритм: выбрать случайный элемент pivot $обычнослучайныйиндекс$, выполнить разбиение $partition$ массива на элементы < pivot и > pivot $и,приобычнойреализации,равныемогутидтивлюбуюизчастей$, затем рекурсивно сортировать части.Характеристики: сравнение-ориентированный, нестабильный в базовом варианте, in-place $всреднемO(logn)дополнительнойпамятинастекрекурсии$.

2) Среднее время работы $рандомизированныйpivot$

Теоретический результат: при выборе pivot равновероятно из текущего подмассива ожидаемое число сравнений — Θ$nlogn$. Более точная асимптотика числа сравнений:
E[#сравнений] = 2 n ln n + O$n$ $натуральныйлогарифм$. Это ~1.386 n log2 n + O$n$.Следовательно, ожидаемое время работы Θ$nlogn$. Константы хорошие, поэтому на практике быстрая сортировка очень эффективна.

3) Худшее время работы

В худшем случае $систематическиоченьнеудачныеразбиения:одинподмассивразмерn-1,другой0$ сложность — Θ$n^2$ $примерноn(n-1)/2сравнений$.Для детерминированного выбора опоры $например,всегдапервый/последнийэлемент$ вход, уже отсортированный или обратно отсортированный, даёт худший случай.При настоящем случайном выборе опоры вероятность получить последовательность крайне неудачных разбиений на каждом шаге экспоненциально мала. То есть рандомизированный алгоритм имеет квадратичное время, но с очень малой вероятностью; с высокой вероятностью $w.h.p.$ время — Θ$nlogn$.

4) Влияние выбора опоры

Случайный pivot:
защищает от злонамеренных / специфичных входов $нетвозможностизаранееподобратьвход,приводящийвсегдакхудшемуслучаю$;даёт хорошее среднее поведение и низкую среднюю глубину рекурсии $O(logn)всреднем$.Медиана по трём $median-of-three$:
берётся медиана из трёх элементов $например,первый,средний,последний$ — уменьшает шанс плохих разбиений на «почти отсортированных» входах, снижает константу.всё ещё не обеспечивает гарантий — могут существовать входы, которые обманывают этот выбор.Дет. выбор медианы $median-of-medians$:
даёт детерминированную выборку приблизительной медианы за O$n$ и позволяет обеспечить худший случай Θ$nlogn$ при каждой рекурсии, но накладные расходы значительны; редко используется в практической сортировке из-за больших констант.

5) Влияние повторяющихся ключей

Проблема: при большом числе равных ключей двухчастное partition (разбить на < и >= либо <= и >) часто создаёт очень несимметричные разбиения, т.к. равные элементы попадают в одну из сторон, что может привести к ухудшению производительности $вплотьдоквадратичной$.Решение: трёхпутевая $3-way$ сортировка $Dutchnationalflag$:
Разбивает на три части: < pivot, = pivot, > pivot. Затем рекурсивно сортирует только меньшую и большую части.При многих равных ключах эффективно — если все элементы одинаковы, алгоритм работает за Θ$n$ $проходитпоэлементамодинраз$.Рекомендуется всегда использовать 3-way-партиционирование, если ожидаются повторяющиеся ключи.

6) Практические адаптации для устойчивой производительности
Рекомендуемый гибрид и инженерные приёмы $частоприменяемыевбиблиотечныхреализациях$:

Рандомизация

Выбирать pivot как случайный элемент $изтекущегоподмассива$. Это простая и эффективная защита от худших случаев на специально подобранных входах.

Трёхпутевая партиция

Использовать Dijkstra 3-way partition, если возможны повторяющиеся ключи — это существенно улучшает поведение при дубликатах.

Интроспективная сортировка $introsort$

Запускать quicksort с рандомным pivot или median-of-three; если глубина рекурсии превышает c·log n $например,2\cdot \lfloor log2n\rfloor$, переключаться на heapsort. Это даёт гарантированный O$nlogn$ худший случай и при этом сохраняет хорошие средние константы quicksort.Этот подход используется в многих стандартных реализациях $например,вlibstdc++/std::sort—снекоторымивариациями$.

Порог для малых подмассивов

Для маленьких подмассивов $обычноразмер\le 10–32$ лучше применять insertion sort — у него низкие константы и высокая локальность памяти.Типичное сочетание: quicksort + insertion sort как финальный шаг.

Выбор опоры: median-of-three

Для невраждебных входов median-of-three часто даёт лучшую практическую константу, чем полностью случайный pivot $меньшесравнений$, но не защищает от всех паттернов.

Хвостовая оптимизация и итеративная реализация

Рекурсию заменить на итерацию для одной стороны $tailrecursionelimination$ и всегда рекурсивно обрабатывать меньшую часть — гарантирует O$logn$ глубину стека в среднем, снижает риск переполнения стека.

Стабильность

Стандартный inplace quicksort нестабилен. Для стабильности нужно дополнительная память $например,stablequicksort/mergesortгибриды$ или сортировка пар $ключ,исходныйиндекс$.

Параллелизм и кеширование

Блоковая партиция и внимание к локальности данных улучшают скорость на современных кэшах. Для больших данных — распараллеливание рекурсивных вызовов.

7) Конкретная рекомендуемая конфигурация для практических реализаций

Использовать рандомный pivot или median-of-three.Делать 3-way partition при возможных дубликатах.Обрабатывать меньшую часть рекурсивно, большую итеративно $tailcall$.Если глубина рекурсии > c·log n, переключаться на heapsort $introsort$.Для подмассивов размера ≤ 16 — insertion sort.При необходимости стабильности — использовать stable sort $merge-based$ либо stable quicksort с доп. памятью.

8) Итоги по сложностям

Ожидаемое время: Θ$nlogn$ (E[#сравнений] ≈ 2 n ln n + O(n)).Худшее время: Θ$n^2$ для классического quicksort; при использовании introsort — гарантированно Θ$nlogn$.Память: in-place, дополнительная стек-память Θ$logn$ в среднем; в худшем случае O$n$ $еслинеприменятьtail-callизащиту$.Поведение при дубликатах: без 3-way — может ухудшаться; с 3-way — быстрое $влучшемслучае\Theta (n)привсехравных$.

9) Короткие псевдокоды $схема$

Рандомизированный quicksort $двухчастныйpartition$:

if n ≤ threshold: insertion_sortpivot_index = random$lo..hi$; swap$a[lo],a[pivo{t}_{i}ndex]$p = partition$a,lo,hi$ // возвращает границуrecurse left, right $обрабатыватьменьшуючастьрекурсивно$

Трёхпутевая партиция $Dutchflag$:

lt = lo; i = lo; gt = hi;pivot = a$$random(lo..hi)$$;while i ≤ gt:
if a$$i$$ < pivot: swap$a[lt],a[i]$; lt++; i++;
else if a$$i$$ > pivot: swap$a[i],a[gt]$; gt--;
else: i++;recurse on $lo..lt-1$ and $gt+\mathrm{1..}hi$

10) Небольшие замечания по реализации

Источник случайности: можно использовать xorshift/LCG для скорости; при желании воспроизводимости — фиксированный seed.Для числовых типов и простых структур median-of-three бывает быстрее на практике; для сложных ключей random+3-way чаще предпочтительнее.Профилируйте для конкретных данных — в реальности «лучший» набор оптимизаций зависит от распределения ключей и требований $память,стабильность,кэш$.

Если хотите, могу:

Привести пример кода $C/C++/Python$ для варианта: randomized quicksort + 3-way partition + introsort-переход + insertion sort для мелких массивов.Сравнить по числам сравнений и времени несколько конфигураций на различных распределениях данных $равномернослучайные,ужеотсортированные,сдубликатами$.