VMware安装Ubuntu实战分享大纲

深入解析快速排序

一、分治策略分解

1. 分解阶段：

   • 选择基准元素 $pivot$
   • 将数组划分为三个子集： $$ left = {x | x < pivot} $$ $$ equal = {x | x = pivot} $$ $$ right = {x | x > pivot} $$

2. 递归排序：

   • 对 left 和 right 子集递归调用快速排序
   • 递归终止条件：当子集长度 $\leq 1$ 时直接返回

3. 合并结果： $$ 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)$

三、基准选择优化

1. 随机选择法：

   import random
   pivot_index = random.randint(0, len(arr)-1)
   arr[0], arr[pivot_index] = arr[pivot_index], arr[0]  # 交换到首位
   

2. 三数取中法：

   • 取首、中、尾三个元素
   • 选择中间值作为基准

3. 中位数法：

   • 每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]

五、工程优化技巧

1. 混合排序：当子数组长度 < 15 时切换为插入排序
2. 尾递归优化：减少递归调用栈深度
3. 重复元素处理：三向切分法（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)$

七、实际应用场景

1. 内置排序算法实现（如Java的Arrays.sort()）
2. 大数据排序（结合外排序技术）
3. 需要原地排序的场合（内存受限环境）
4. 快速选择算法（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]))

注：这种方法会破坏原地排序特性，但能保持稳定性