快速排序算法详解
快速排序是一种基于分治策略的高效排序算法，由Tony Hoare于1959年提出。其核心思想是通过递归地将数据分割成较小和较大的子序列来实现排序。算法平均时间复杂度为$O(n \log n)$，在最坏情况下为$O(n^2)$，但通过优化可避免最坏情况。
算法原理
- 选择基准：从数组中任选一个元素作为基准值（pivot）
- 分区操作：将数组分为三部分：
- 小于基准值的元素
- 等于基准值的元素
- 大于基准值的元素
- 递归排序：对小于和大于基准值的子数组递归进行快速排序
分区操作的数学表达式可表示为： $$ \text{left} = { x \in \text{arr} \mid x < \text{pivot} } $$ $$ \text{right} = { x \in \text{arr} \mid x > \text{pivot} } $$
优化实现
基础版本需要额外存储空间，以下是原地排序的优化实现：
def partition(arr, low, high): """分区函数实现原地排序""" pivot = arr[high] # 选择最后一个元素作为基准 i = low - 1 # 小于基准的边界指针 for j in range(low, high): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] # 交换位置 arr[i+1], arr[high] = arr[high], arr[i+1] # 基准归位 return i + 1 def quick_sort_inplace(arr, low, high): """原地快速排序主函数""" if low < high: pi = partition(arr, low, high) # 获取基准位置 quick_sort_inplace(arr, low, pi-1) # 递归左子数组 quick_sort_inplace(arr, pi+1, high) # 递归右子数组 # 封装调用接口 def optimized_quick_sort(arr): quick_sort_inplace(arr, 0, len(arr)-1) return arr时间复杂度分析
- 最优情况：每次分区平衡时 $T(n) = 2T(n/2) + O(n)$，解得 $O(n \log n)$
- 最坏情况：已排序数组且选择端点 $T(n) = T(n-1) + O(n)$，解得 $O(n^2)$
- 空间复杂度：优化后为 $O(\log n)$（递归栈深度）
扩展应用
# 三路快速排序（处理重复元素） def quick_sort_3way(arr): if len(arr) <= 1: return arr pivot = arr[len(arr)//2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort_3way(left) + middle + quick_sort_3way(right) # 测试用例 test_array = [3, 6, 8, 10, 1, 2, 1] print("基础版本:", quick_sort(test_array.copy())) print("优化版本:", optimized_quick_sort(test_array.copy())) print("三路排序:", quick_sort_3way(test_array.copy()))算法特性
- 稳定性：基础版本不稳定，三路版本可保持稳定
- 适用场景：大规模乱序数据，内存受限环境（优化版本）
- 优化技巧：
- 随机选择基准避免最坏情况
- 小数组切换为插入排序
- 三数取中法选择基准
通过合理选择基准和优化实现，快速排序在实践中通常优于归并排序和堆排序，是多数编程语言标准库的默认排序实现。
