教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载快速排序Quick Sort是 AlgoNote「算法通关手册」数组排序章节的核心算法之一它基于分治策略通过选取基准值将数组划分为左右两个子数组并递归排序平均时间复杂度为 $O(n \log n)$且为原地排序。本文结合仓库文档 docs/01_array/01_08_array_quick_sort.md 与源码 array_sort_quick_sort.py系统讲解其算法思想、分区步骤、完整 Python 实现、复杂度分析与优化策略并串联 0912. 排序数组 与 0169. 多数元素 两道 LeetCode 实战题目帮助读者彻底掌握这一面试高频排序算法。一、快速排序算法思想快速排序Quick Sort基本思想采用分治策略选择一个基准元素将数组分为两部分——小于基准的元素放在左侧大于基准的元素放在右侧然后递归地对左右两部分进行排序最终得到有序数组。快速排序与归并排序同属 $O(n \log n)$ 级别的分治排序算法但二者有一个关键区别归并排序先递归拆分再在「合并」阶段完成排序需要额外的 $O(n)$ 空间快速排序在「划分」阶段即哨兵划分就完成了大部分排序工作递归结束后数组整体即有序整个过程原地进行空间开销主要来自递归调用栈。在 AlgoNote 的排序算法体系中参见 01.02 数组排序快速排序被归类为原地排序且不稳定的高级排序算法是大规模数据与高性能场景的首选之一。二、快速排序算法步骤哨兵划分 递归分解快速排序的核心是分区操作哨兵划分其完整步骤如下选择基准从数组区间中选择一个元素作为基准值pivot通常选择区间的第一个元素即pivot nums[low]。分区操作双指针法左指针i指向区间起点low右指针j指向区间终点high右指针j从右向左移动找到第一个小于基准值的元素左指针i从左向右移动找到第一个大于基准值的元素交换这两个元素重复上述过程直到左右指针相遇将基准值放到正确位置左右指针相遇处。递归排序对基准值左右的两个子数组分别递归执行快速排序直到子数组长度为 1排序结束。一次分区完成后数组被划分为三部分左子数组全部 ≤ 基准、基准值已就位、右子数组全部 ≥ 基准且基准值已经处于其最终有序位置后续递归不再移动它。三、图解分区过程以数组[4, 7, 5, 2, 6, 1, 3]为例原文档以[4, 7, 5, 2, 6, 1, 3]为例演示了分区操作的全过程核心流程可归纳为下表基准值取首元素4轮次操作数组状态*为基准值i/j为指针位置初始选取基准值pivot 4i指向low0j指向high6[4*, 7, 5, 2, 6, 1, 3]1j左移找到第一个小于 4 的元素3下标 6[4, 7, 5, 2, 6, 1, 3]2i右移找到第一个大于 4 的元素7下标 1交换7与3[4, 3, 5, 2, 6, 1, 7]3j继续左移找到小于 4 的1下标 5i右移找到大于 4 的5下标 2交换[4, 3, 1, 2, 6, 5, 7]4j左移找到小于 4 的2下标 3此时i与j相遇[4, 3, 1, 2, 6, 5, 7]5将基准值4与相遇位置元素2交换4落位[2, 3, 1, 4, 6, 5, 7]第一趟分区结束后数组被分为左子数组[2, 3, 1]、基准值4、右子数组[6, 5, 7]。随后分别对左右两个子数组递归执行同样的「选择基准 → 双指针分区 → 落位」过程最终得到完全有序的数组[1, 2, 3, 4, 5, 6, 7]。四、快速排序 Python 代码实现仓库源码对照仓库在 codes/python/01_array/array_sort_quick_sort.py 中提供了可运行的完整实现与文档代码一致。实现采用「随机选择基准值 哨兵划分」组合具体如下import random class Solution: # 随机哨兵划分从 nums[low: high 1] 中随机挑选一个基准数并进行移位排序 def randomPartition(self, nums: [int], low: int, high: int) - int: # 随机挑选一个基准数 i random.randint(low, high) # 将基准数与最低位互换 nums[i], nums[low] nums[low], nums[i] # 以最低位为基准数然后将数组中比基准数大的元素移动到基准数右侧比他小的元素移动到基准数左侧。最后将基准数放到正确位置上 return self.partition(nums, low, high) # 哨兵划分以第 1 位元素 nums[low] 为基准数然后将比基准数小的元素移动到基准数左侧将比基准数大的元素移动到基准数右侧最后将基准数放到正确位置上 def partition(self, nums: [int], low: int, high: int) - int: # 以第 1 位元素为基准数 pivot nums[low] i, j low, high while i j: # 从右向左找到第 1 个小于基准数的元素 while i j and nums[j] pivot: j - 1 # 从左向右找到第 1 个大于基准数的元素 while i j and nums[i] pivot: i 1 # 交换元素 nums[i], nums[j] nums[j], nums[i] # 将基准数放到正确位置上 nums[j], nums[low] nums[low], nums[j] return j def quickSort(self, nums: [int], low: int, high: int) - [int]: if low high: # 按照基准数的位置将数组划分为左右两个子数组 pivot_i self.partition(nums, low, high) # 对左右两个子数组分别进行递归快速排序 self.quickSort(nums, low, pivot_i - 1) self.quickSort(nums, pivot_i 1, high) return nums def sortArray(self, nums: [int]) - [int]: return self.quickSort(nums, 0, len(nums) - 1) print(Solution().sortArray([4, 7, 5, 2, 6, 1, 3]))4.1 关键函数解析partition(nums, low, high)哨兵划分函数返回基准值的最终索引。它以区间首元素nums[low]为基准通过双指针i、j从两端向中间收缩j负责寻找小于基准的元素i负责寻找大于基准的元素找到后交换当i与j相遇时把基准值与相遇位置元素交换此时基准值左侧全部不大于它、右侧全部不小于它。注意两个内层循环都带i j条件保证指针不会越界相交。randomPartition(nums, low, high)先用random.randint(low, high)在区间内随机挑选一个索引与low处元素互换再调用partition。随机化基准值是规避最坏情况如对已排序数组的关键手段。quickSort(nums, low, high)递归主函数low high为递归继续的条件每次根据partition返回的基准位置pivot_i将区间拆为[low, pivot_i - 1]与[pivot_i 1, high]两个子区间分别递归排序。sortArray(nums)对外入口以0和len(nums) - 1作为初始区间调用quickSort。4.2 运行验证源码文件末尾直接附带了测试调用print(Solution().sortArray([4, 7, 5, 2, 6, 1, 3]))在 Python 3 环境中直接运行该文件即可输出[1, 2, 3, 4, 5, 6, 7]与文档第 3 节的示例数据完全对应便于读者即时验证算法正确性。五、快速排序算法复杂度分析指标复杂度说明最佳时间复杂度$O(n \log n)$每次都能将数组平均分成两半递归深度为 $\log n$最坏时间复杂度$O(n^2)$每次选择的基准值都是极值如对已排序数组选取首元素为基准平均时间复杂度$O(n \log n)$随机选择基准值时的期望复杂度空间复杂度$O(\log n)$递归栈空间最坏情况下为 $O(n)$稳定性不稳定交换操作可能改变相等元素的相对位置关于空间复杂度需要补充说明快速排序是原地排序仅靠元素交换不申请额外数组额外空间全部来自递归调用栈。平均递归深度为 $O(\log n)$因此空间复杂度为 $O(\log n)$但在基准选择极端失衡时递归深度退化为 $O(n)$。这也是为什么工程实现中普遍采用随机化或三数取中来保证基准选择的均衡性。六、适用场景与优化策略6.1 适用场景大规模数据排序$n \geq 1000$此时 $O(n^2)$ 的简单排序算法已不可接受对平均性能要求高的场景期望复杂度稳定在 $O(n \log n)$数据分布相对均匀的情况分区较为均衡内存受限环境作为原地排序算法不需要归并排序那样的额外 $O(n)$ 数组空间。6.2 优化策略随机选择基准值从区间内随机取一个元素作为基准即上文源码中的randomPartition从概率上避免最坏情况三数取中法选择基准值取区间首、中、尾三个元素的中位数作为基准进一步平滑数据分布带来的退化风险小数组使用插入排序当子区间规模足够小如小于某个阈值时切换为插入排序减少递归开销因为插入排序在小型数据上常数因子更小处理重复元素时使用三路快排将数组划分为「小于基准 / 等于基准 / 大于基准」三段避免大量相等元素反复参与分区显著提升重复数据场景的性能。七、源码佐证LeetCode 实战与链表扩展7.1 0912. 排序数组十种排序算法大考仓库题解 sort-an-array.md 是检验排序算法真实性能的经典题目数组长度上限 $5 \times 10^4$值域 $[-5 \times 10^4, 5 \times 10^4]$。题解作者实测了十种排序算法结论包括超时$O(n^2)$冒泡排序、选择排序、插入排序通过$O(n \log n)$希尔排序、归并排序、快速排序、堆排序通过$O(n)$计数排序、桶排序解答错误普通基数排序只适合非负数。其中「思路 6快速排序通过」给出了与本文一致的随机化快速排序完整代码并详细拆解了「哨兵划分 → 递归分解」两步流程。这从实战角度印证了随机化快速排序在大规模数据上是可靠且高效的 $O(n \log n)$ 算法。7.2 0169. 多数元素分治思想的再次运用多数元素题解 中给出的「思路 2分治算法」与快速排序共享同一套分治方法论将数组递归拆分为左右两半利用「若某个数是整个区间的众数则它至少是某一半的众数」的性质逐层合并求解。这篇题解可以作为复习分治思想的配套练习。7.3 链表上的快速排序快速排序同样可以应用于链表场景仓库在 02.07 链表快速排序 与源码 linked_list_quick_sort.py 中给出了实现以头节点值为基准用node_i、node_j快慢指针遍历链表完成就地分区只交换节点值不改变节点连接再对[left, pi)与[pi.next, right)两个开区间递归排序。需要注意链表快速排序的复杂度和稳定性特征与数组版一致平均 $O(n \log n)$、最坏 $O(n^2)$、不稳定题解 0148. 排序链表 提示该写法在 LeetCode 上会超时仅作为练习。八、总结快速排序的优缺点快速排序是一种高效的排序算法采用分治策略通过分区操作将数组分成两部分然后递归排序。优点平均情况下效率高时间复杂度为 $O(n \log n)$原地排序空间复杂度低平均 $O(\log n)$ 递归栈缓存友好局部性良好实际应用中常数因子较小是许多编程语言内置排序函数的实现基础。缺点不稳定排序相等元素的相对顺序可能改变最坏情况下性能较差时间复杂度退化为 $O(n^2)$可通过随机基准、三数取中等策略缓解对于小数组插入排序等简单算法可能更快递归调用可能导致栈溢出可结合尾递归优化或改迭代实现规避。综合来看快速排序以优秀的平均性能、原地排序特性和良好的缓存局部性在通用排序领域占据核心地位。理解其分治思想、哨兵划分细节与随机化优化策略既是应对算法面试的基本功也是深入理解工程排序库实现如基于快排思想的快速选择算法的基石。练习题目与延伸阅读0912. 排序数组快速排序实战0169. 多数元素分治练习排序算法题目列表按分类刷题数组排序算法总览01.02链表快速排序分治思想的链表实现赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐Cosmos 项目 Quicksort 快速排序详解分治思想、分区算法与多语言实现Cosmos 项目 Quicksort 快速排序详解分治思想、分区算法与多语言实现 Quicksort快速排序是 Cosmos 算法库中排序模块的核心算法教程示例工程OAuth2 Proxy Alpha 配置完全指南基于 YAML 的结构化配置迁移与使用实战OAuth2 Proxy Alpha 配置完全指南基于 YAML 的结构化配置迁移与使用实战 OAuth2 Proxy 从 7.x 版本开始引入了全新的 Al教程文档知识库AlgoNote「算法通关手册」二分查找算法详解——从减而治之思想到有序数组搜索实战AlgoNote「算法通关手册」二分查找算法详解——从减而治之思想到有序数组搜索实战 二分查找Binary Search是《算法通关手册》数组章节中第一个教程文档知识库上一篇openEuler社区检查从未如此简单easy-checker用户实战案例下一篇如何快速部署KubeHawk5分钟上手云原生监控利器创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
