快速排序 (Quick Sort)分治法的经典应用摘要冒泡排序和鸡尾酒排序每轮只能消除相邻逆序对复杂度卡在 O(n²)。快速排序引入分治思想——选一个基准将数组分为小于基准和大于基准两部分递归排序。本文从分区思想出发图解三数取中基准选择与 Lomuto 分区方案给出支持升序/降序的 Python 完整实现对比不同基准策略的性能差异并分析工业级排序IntroSort、Dual-Pivot Quicksort的工程实践。本文属于专栏《算法》系列 1 第 3 篇 | 上一篇鸡尾酒排序 (Cocktail Sort)| 下一篇1-4-归并排序-MergeSort文章目录快速排序 (Quick Sort)分治法的经典应用一、问题引入二、算法原理图解核心思想基准选择策略Lomuto 分区方案图解递归过程与前两篇算法的对比三、代码实现基础版首元素作基准进阶版三数取中 Lomuto 分区 原地排序运行验证四、复杂度分析时间复杂度空间复杂度稳定性五、横向对比基准选择策略对比六、工程实战标准库中的快速排序IntroSort快排的工程进化Dual-Pivot Quicksort为什么 Python 不用快速排序七、常见误区与面试题高频面试题常见实现错误八、总结一、问题引入前面两篇文章中冒泡排序和鸡尾酒排序的核心操作都是比较相邻元素并交换。这种方式有一个根本限制每次交换只能消除一个相邻逆序对因此总比较/交换次数至少是 O(n²)。能否一步到位让一次分区操作同时处理多个逆序对考虑数组[5, 3, 8, 1, 2]冒泡排序第 1 轮比较 4 次只把 8 移到末尾如果我们选 5 作为基准把小于 5 的放左边、大于 5 的放右边一次分区就得到[3, 1, 2, 5, 8]——5 到了正确位置左侧 3 个元素和右侧 1 个元素各自递归处理即可这就是快速排序的核心思想分而治之。选一个基准 (pivot)将数组分为两部分递归排序。问题定义输入含 n 个元素的可比较数组arr输出按升序或降序排列的数组核心操作选基准 → 分区 → 递归二、算法原理图解核心思想快速排序的三步分治选基准 (Choose Pivot)从数组中选一个元素作为基准分区 (Partition)将小于基准的元素放左边大于基准的放右边基准归位到最终正确位置递归 (Recurse)对左右两部分分别递归执行快速排序基准选择策略基准选得好坏直接决定分区是否平衡进而决定时间复杂度策略说明风险取首/尾元素最简单已有序数组退化为 O(n²)取中间元素简单特定分布仍可能不平衡随机取基准概率上避免最坏随机数生成开销三数取中取首、中、尾的中值实践中最常用开销小本文采用三数取中法取low、mid、high三个位置的中值作为基准兼顾简单与效率。Lomuto 分区方案分区有多种实现本文使用最易理解的Lomuto 分区以 [5, 3, 8, 1, 2] 升序排序为例三数取中选 5 作为基准 步骤 1三数取中 → low5, mid8, high2中值为 5 步骤 2基准交换到 high → [2, 3, 8, 1, 5]基准 5 放到末尾 步骤 3单指针扫描分区 i0, j0: arr[0]2 ≤ 5放左 → [2, 3, 8, 1, 5], i1 i1, j1: arr[1]3 ≤ 5放左 → [2, 3, 8, 1, 5], i2 i2, j2: arr[2]8 5跳过 i2, j3: arr[3]1 ≤ 5交换 → [2, 3, 1, 8, 5], i3 步骤 4基准归位 → 交换 arr[3] 和 arr[4] [2, 3, 1, 5, 8] 基准 5 到达最终位置 index3 分区结果左 [2, 3, 1] | 5 | 右 [8]图解递归过程[5, 3, 8, 1, 2] 选基准 5分区 ↓ [2, 3, 1] 5 [8] 选基准 2 ✓ ✓单元素 ↓ [1] 2 [3] ✓ ✓单元素 最终结果: [1, 2, 3, 5, 8]整个排序仅需 2 次分区 2 次递归对比冒泡排序需要 4 轮完整扫描。与前两篇算法的对比维度冒泡排序鸡尾酒排序快速排序核心策略相邻比较交换双向相邻交换分区 递归每轮消除逆序对1 个相邻1 个相邻多个跨区间平均时间O(n²)O(n²)O(n log n)空间O(1)O(1)O(log n)递归栈稳定性稳定稳定不稳定三、代码实现完整代码通过网盘分享的文件算法链接: https://pan.baidu.com/s/1DTJt1X2Is_IQeH5fAXvtZg?pwdyyqf 提取码: yyqf–来自百度网盘超级会员v4的分享基础版首元素作基准defquick_sort_basic(arr):基础快速排序取首元素作基准无优化iflen(arr)1:returnarr pivotarr[0]left[xforxinarr[1:]ifxpivot]right[xforxinarr[1:]ifxpivot]returnquick_sort_basic(left)[pivot]quick_sort_basic(right)这是最直观的写法但有两个问题不是原地排序每次创建新列表且对已有序数组退化为 O(n²)。进阶版三数取中 Lomuto 分区 原地排序defquick_sort(arr,ascendingTrue): 快速排序分治法选基准分区将小于基准的放左侧、大于基准的放右侧 递归排序左右两部分。 时间复杂度平均 O(n log n)最坏 O(n²) | 空间复杂度O(log n) | 不稳定排序 参数: arr: 待排序列表 ascending: 排序方向True升序默认False降序 返回: 排序后的列表原地排序 _quick_sort_recursive(arr,0,len(arr)-1,ascending)returnarrdef_median_of_three(arr,low,high,ascending): 三数取中法选择基准索引取 low、mid、high 三个位置的中值作为基准 避免最坏情况如已有序数组导致分区极度不平衡。 返回: 基准元素的索引 mid(lowhigh)//2# 取三个候选值找出中间值对应的索引candidates[(low,arr[low]),(mid,arr[mid]),(high,arr[high])]# 升序按值排序取中间降序同理中间值不变只是排序方向不同candidates.sort(keylambdax:x[1],reversenotascending)returncandidates[1][0]def_partition(arr,low,high,ascending): Lomuto 分区方案以 arr[pivot_idx] 为基准将其移到 high 位置 然后从左到右扫描把满足条件的元素交换到左侧。 分区结束后基准位于正确位置左侧全比基准小升序右侧全比基准大。 返回: 基准元素的最终位置索引 # 三数取中选基准与 high 交换pivot_idx_median_of_three(arr,low,high,ascending)arr[pivot_idx],arr[high]arr[high],arr[pivot_idx]pivotarr[high]# i 指向已分好区的右边界即下一个可放置元素的位置ilowforjinrange(low,high):# 升序小于基准放左降序大于基准放左should_placearr[j]pivotifascendingelsearr[j]pivotifshould_place:arr[i],arr[j]arr[j],arr[i]i1# 将基准放到最终正确位置arr[i],arr[high]arr[high],arr[i]returnidef_quick_sort_recursive(arr,low,high,ascending):递归排序 [low, high] 区间。iflowhigh:returnpivot_pos_partition(arr,low,high,ascending)_quick_sort_recursive(arr,low,pivot_pos-1,ascending)_quick_sort_recursive(arr,pivot_pos1,high,ascending)三个关键设计三数取中选基准从low、mid、high取中值避免已有序数组退化为 O(n²)Lomuto 分区单指针i标记已分好区的右边界扫描一遍完成分区代码简洁原地排序通过索引操作和原地交换空间复杂度仅 O(log n)递归栈运行验证if__name____main__:data[64,34,25,12,22,11,90]print(f排序前:{data})print(f升序:{quick_sort(data[:])})print(f降序:{quick_sort(data[:],ascendingFalse)})输出排序前: [64, 34, 25, 12, 22, 11, 90] 升序: [11, 12, 22, 25, 34, 64, 90] 降序: [90, 64, 34, 25, 22, 12, 11]四、复杂度分析时间复杂度情况复杂度说明最好O(n log n)每次基准恰好将数组等分递归树高度 log n每层 O(n)平均O(n log n)随机数据下期望分区比较均衡最坏O(n²)每次基准都是最值分区极度不平衡如已有序 取首元素推导过程最好情况每次等分第 1 层n 个元素分区比较 n-1 次 第 2 层2 × (n/2) 个元素分区比较 2 × (n/2 - 1) ≈ n 次 第 3 层4 × (n/4) 个元素分区比较 ≈ n 次 ... 第 log n 层n 个单元素比较 0 次 总比较次数 ≈ n × log n O(n log n)最坏情况推导每次选到最值分区退化为 1 n-1第 1 次分区n-1 次比较分为 0 和 n-1 第 2 次分区n-2 次比较分为 0 和 n-2 ... 总比较次数 (n-1) (n-2) ... 1 n(n-1)/2 O(n²)三数取中优化的作用对于已有序数组[1,2,3,...,n]取首、中、尾三数的中值基准不再是极端最值分区接近平衡避免了 O(n²) 退化。空间复杂度O(log n)——递归调用栈的深度。最好情况下递归树高度为 log n最坏情况下无优化退化为 n。三数取中将最坏情况的概率降到极低。稳定性不稳定排序。分区过程中元素跨越基准位置交换相等元素的相对顺序可能被改变。例如[3a, 3b, 1]选 3a 为基准分区后[1, 3a, 3b]看似稳定。但如果基准选择或交换顺序不同相等元素可能交叉。五、横向对比快速排序与同系列算法的对比算法平均时间最好时间最坏时间空间稳定性特点冒泡排序O(n²)O(n)O(n²)O(1)稳定最简单适合教学鸡尾酒排序O(n²)O(n)O(n²)O(1)稳定双向扫描缓解乌龟问题快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定工业界默认选择归并排序O(n log n)O(n log n)O(n log n)O(n)稳定稳定且始终 O(n log n)堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定原地排序常数较大基准选择策略对比策略随机数据已有序数据重复元素多实现难度取首元素O(n log n)O(n²)O(n²)最简单随机取O(n log n)O(n log n)O(n²)简单三数取中O(n log n)O(n log n)O(n²)中等双轴快排O(n log n)O(n log n)O(n log n)复杂选型建议通用场景首选快速排序三数取中优化平均性能最优需要稳定排序时选择归并排序或 TimSort内存受限场景选择堆排序O(1) 空间小规模数据n 20插入排序的常数因子更小六、工程实战标准库中的快速排序快速排序是工业级排序的基石几乎所有标准库都基于它语言排序函数策略Cstd::sortIntroSort快排 堆排 插入排序的自适应组合JavaArrays.sort()基本类型用 Dual-Pivot Quicksort对象用 TimSortCqsort()通常为快速排序实现Pythonlist.sort()TimSort归并 插入非快排但受快排启发IntroSort快排的工程进化Cstd::sort使用的 IntroSort 是快排的终极进化版默认用快速排序平均性能最优检测递归深度超过 2×log₂n 层时切换为堆排序保证最坏 O(n log n)小区间切换插入排序当区间小于 16 个元素时用插入排序减少递归开销Dual-Pivot QuicksortJava 对基本类型使用双轴快速排序选两个基准P1和P2P1 P2将数组分为三部分[ P1] [P1 ≤ x ≤ P2] [ P2]三路分区在重复元素多的场景下效率更高这也是 Arrays.sort() 对基本类型选择它而非 TimSort 的原因。为什么 Python 不用快速排序Python 的list.sort()使用 TimSort 而非快速排序原因有二稳定性Python 排序默认稳定快速排序不稳定部分有序数据现实数据常有部分有序片段TimSort 能利用这种结构达到接近 O(n) 的性能七、常见误区与面试题高频面试题Q1快速排序为什么快快速排序的平均时间复杂度 O(n log n) 与归并排序、堆排序相同但实际运行更快原因是缓存友好分区是顺序扫描局部性好CPU 缓存命中率高常数因子小每次分区只做比较和交换没有归并排序的额外数组拷贝原地排序不像归并排序需要 O(n) 额外空间Q2快速排序的最坏情况是什么如何避免最坏情况是每次选到最值作为基准分区退化为 0 (n-1)复杂度退化为 O(n²)。常见触发场景数组已有序 取首/尾元素作基准数组全相同某些分区方案避免方法三数取中法、随机取基准、IntroSort检测深度后切换堆排。Q3Lomuto 分区和 Hoare 分区有什么区别维度Lomuto 分区Hoare 分区指针单指针 i双指针 i, j 相向扫描比较次数每轮 n-1 次每轮约 n/2 次更少交换次数较多较少代码复杂度简单稍复杂基准最终位置一定是分区点不一定是分区点Q4快速排序是稳定的吗为什么不稳定。分区过程中元素跨距离交换相等元素的相对顺序可能被改变。例如[5a, 5b, 3]选 5a 为基准分区后[3, 5a, 5b]看似稳定但其他分区方案可能产生[3, 5b, 5a]。常见实现错误错误说明修正取首元素作基准不优化已有序数组退化为 O(n²)使用三数取中或随机取基准分区条件写成而非大量重复元素时分区极度不平衡用将等于基准的元素也放左侧递归终止条件写错low high漏掉等于的情况应为low high单元素无需排序忘记原地交换用列表推导创建大量临时列表空间 O(n log n)用索引操作和原地交换八、总结快速排序的核心要点分治思想——选基准、分区、递归将问题分解为子问题三数取中优化——避免已有序数据退化为 O(n²)实践中最常用Lomuto 分区——单指针扫描代码简洁适合教学和面试手撕平均 O(n log n) 但不稳定——实际运行最快但牺牲了稳定性工业级进化——IntroSortC、Dual-PivotJava在快排基础上进一步优化快速排序是从 O(n²) 到 O(n log n) 的关键跨越。理解了分区思想后续的归并排序另一种分治、堆排序利用堆结构选择都能在此基础上自然对比。专栏导航算法⬅️上一篇鸡尾酒排序 (Cocktail Sort) ➡️下一篇1-4-归并排序-MergeSort如果这篇文章对你有帮助欢迎点赞、收藏、关注支持专栏持续更新文章标签算法排序算法快速排序分治法Python面试