逆序对计数与快速排序

这两个问题都使用分治，但“合并”的位置完全不同：逆序对在递归返回时合并统计；快速排序先用分区确定主元，再递归处理两侧。

1. 逆序对

对数组 $A[1..n]$，若 $i<j$ 且 $A_i>A_j$，则 $(i,j)$ 是一个逆序对。逆序对数量衡量序列偏离升序的程度。

直接枚举所有下标对需要 $\Theta(n^2)$。

2. 归并时统计跨区逆序对

把数组分成左右两半。逆序对分为：

• 完全在左半区；
• 完全在右半区；
• 左元素与右元素构成的跨区逆序对。

前两类递归计算。合并两个已排序数组 $L,R$ 时：

• 若 $L[i]\le R[j]$，取 $L[i]$，不会新增逆序对；
• 若 $L[i]>R[j]$，由于 $L[i..]$ 有序，后面所有左元素都大于 $R[j]$，一次新增 $|L|-i+1$ 个逆序对。

count = 0
while both sides are nonempty:
    if L[i] <= R[j]:
        take L[i]
    else:
        take R[j]
        count += remaining elements in L

递推式与归并排序相同：

$$T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n).$$

如果把相等元素也算逆序，比较符号才改成严格小于；标准定义不计相等元素。

3. 快速排序的分区

选择一个主元 $p$，把数组重排为：

$$[\text{不大于 }p]\quad p\quad[\text{大于 }p].$$

Lomuto 分区的一种写法：

pivot = A[r]
i = l - 1
for j = l .. r - 1:
    if A[j] <= pivot:
        i += 1
        swap A[i], A[j]
swap A[i + 1], A[r]
return i + 1

循环不变式是：

• $A[l..i]\le pivot$；
• $A[i+1..j-1]>pivot$；
• $A[j..r-1]$ 尚未处理。

循环结束后把主元换到 $i+1$，主元就位。

4. 快速排序

QuickSort(A, l, r):
    if l >= r: return
    q = Partition(A, l, r)
    QuickSort(A, l, q - 1)
    QuickSort(A, q + 1, r)

主元已经处于最终位置，左右两侧互不影响。对子区间归纳即可证明正确性。

5. 最好与最坏情况

若每次恰好平分：

$$T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n).$$

若每次主元都是最小或最大元素：

$$T(n)=T(n-1)+\Theta(n)=\Theta(n^2).$$

例如已经有序的数组配合“固定取末尾主元”，就可能触发最坏情况，递归深度也达到 $n$。

6. 随机化为何有效

随机快速排序先从区间中均匀随机选主元，再做分区。输入即使由对手构造，主元秩仍随机。

分析任意一对元素被比较的概率，可以证明期望比较次数为

$$\mathbb E[C_n] =2(n+1)H_n-4n =\Theta(n\log n).$$

随机化没有消除 $O(n^2)$ 最坏情况，但让它发生的概率极低，并把期望复杂度稳定在 $O(n\log n)$。

7. 重复元素与三路分区

若数组中大量元素等于主元，普通二路分区可能反复处理相等元素。三路分区把区间分成：

$$[<p]\ [=p]\ [>p],$$

只递归处理小于和大于两段。所有元素相等时可从 $O(n^2)$ 改善到 $O(n)$。

8. 归并排序与快速排序比较

特性	归并排序	快速排序
最坏时间	$\Theta(n\log n)$	$\Theta(n^2)$
平均时间	$\Theta(n\log n)$	$\Theta(n\log n)$
数组辅助空间	$O(n)$	期望 $O(\log n)$ 栈
稳定性	可稳定	通常不稳定
缓存局部性	较好	通常更好

实际库实现常结合随机主元、三数取中、小数组插入排序和递归深度保护。