深入解析快速排序
一、分治策略分解
-
分解阶段：
- 选择基准元素 $pivot$
- 将数组划分为三个子集： $$ left = {x | x < pivot} $$ $$ equal = {x | x = pivot} $$ $$ right = {x | x > pivot} $$
-
递归排序：
- 对 left 和 right 子集递归调用快速排序
- 递归终止条件：当子集长度 $\leq 1$ 时直接返回
-
合并结果： $$ sorted_arr = quick_sort(left) + equal + quick_sort(right) $$
二、时间复杂度分析
| 情况 | 时间复杂度 | 发生条件 |
|---|---|---|
| 最优 | $O(n \log n)$ | 每次划分完全平衡 |
| 最差 | $O(n^2)$ | 输入已排序+固定基准选择 |
| 平均 | $O(n \log n)$ | 随机化基准选择 |
数学推导（平均情况）： $$ T(n) = 2T(\frac{n}{2}) + O(n) $$ 应用主定理可得 $T(n) = O(n \log n)$
三、基准选择优化
-
随机选择法：
import random pivot_index = random.randint(0, len(arr)-1) arr[0], arr[pivot_index] = arr[pivot_index], arr[0] # 交换到首位 -
三数取中法：
- 取首、中、尾三个元素
- 选择中间值作为基准
-
中位数法：
- 每9个元素为一组取中位数
- 递归求取近似中位数
四、分区算法对比
Lomuto分区法：
def partition(arr, low, high):pivot = arr[high]i = lowfor j in range(low, high):if arr[j] < pivot:arr[i], arr[j] = arr[j], arr[i]i += 1arr[i], arr[high] = arr[high], arr[i]return i
Hoare分区法（效率更高）：
def partition(arr, low, high):pivot = arr[(low + high) // 2]i = low - 1j = high + 1while True:i += 1while arr[i] < pivot: i += 1j -= 1while arr[j] > pivot: j -= 1if i >= j: return jarr[i], arr[j] = arr[j], arr[i]
五、工程优化技巧
- 混合排序：当子数组长度 < 15 时切换为插入排序
- 尾递归优化：减少递归调用栈深度
- 重复元素处理：三向切分法（Dijkstra提出的荷兰国旗问题解法）
def quick_sort_3way(arr, low, high):if low >= high: returnlt, i, gt = low, low, highpivot = arr[low]while i <= gt:if arr[i] < pivot:arr[lt], arr[i] = arr[i], arr[lt]lt += 1i += 1elif arr[i] > pivot:arr[i], arr[gt] = arr[gt], arr[i]gt -= 1else:i += 1quick_sort_3way(arr, low, lt-1)quick_sort_3way(arr, gt+1, high)
六、空间复杂度分析
- 最优情况：$O(\log n)$ （递归栈深度）
- 最差情况：$O(n)$
- 通过尾递归优化可将空间复杂度稳定在 $O(\log n)$
七、实际应用场景
- 内置排序算法实现（如Java的Arrays.sort()）
- 大数据排序（结合外排序技术）
- 需要原地排序的场合（内存受限环境）
- 快速选择算法（Top K问题）的基础
八、稳定性分析
快速排序是不稳定的排序算法，改进方法：
def stable_quick_sort(arr):if len(arr) <= 1: return arrpivot = arr[0]return (stable_quick_sort([x for x in arr if x < pivot]) +[x for x in arr if x == pivot] +stable_quick_sort([x for x in arr if x > pivot]))
注：这种方法会破坏原地排序特性，但能保持稳定性
)
)
