为什么快排平均 O(n log n)：主定理情况3与随机化

图：以 6 为基准的一次分区过程

快速排序的递推式写作 $T(n)=T(q)+T(n-q-1)+\Theta(n)$，其中 $q$ 是基准最终位置。最坏 $q=0$ 或 $n-1$ 时退化为 $T(n)=T(n-1)+\Theta(n)=\Theta(n^2)$（减法型，主定理不管）。但平均情况下，随机化让 $q$ 均匀分布在 $1..n$，每个划分期望把区间分成"大致两半"。

平均情况的递归树

期望上，每层划分代价 $\Theta(n)$，树的期望深度 $\Theta(\log n)$，于是期望总代价 $\Theta(n\log n)$。这正是主定理"情况3 / 均衡划分"的工程版：随机化把最坏的输入顺序"打散"，让期望划分接近均分。

参考代码：随机化快排

import random

def quicksort(a):
    if len(a)  p]
    return quicksort(left) + mid + quicksort(right)

# 期望 T(n)=Θ(n log n)；最坏（已序且固定首元）才 Θ(n^2)
print(quicksort([5, 2, 4, 6, 1, 3]))

主定理严格说只处理 $aT(n/b)$ 这种"均分"形式；快排的"期望均分"是它的现实映射——随机化让平均就等于主定理的情况2/3。

关联推荐

• 从冒泡到快排：排序算法怎样悄悄决定你电脑的快慢 — 直观理解快排为什么快
• 插入、选择、冒泡排序（KU） — 对比 O(n²) 与 O(n log n) 的分水岭
• 算法与问题求解入门（KU） — 期望复杂度的思想起点