★ FEATURED ARTICLE 先说结论快速排序这叫法容易让人以为它天生就快。但快是有前提的枢轴选得怎么样直接决定它是 O(n log n) 还是 O(n²)。固定拿第一个元素当枢轴是最直觉、也最容易埋雷的写法——平时刷题对随机测试数据可能一切正常一旦用例里塞进去一个已经排好序的数组性能立刻崩盘严重的连递归深度都扛不住。这篇文章就把以第一个元素为枢轴实现快速排序这件事讲透从最直观的实现开始分析它为什么会退化然后给出随机化、三数取中、混合策略、迭代版等一系列补救方案。不管你是刚学排序算法的新手还是想在面试前把快排细节完全吃透这篇都值得收藏下来对着敲一遍。1. 快排的分区逻辑枢轴不是参考值而是占位符1.1 一次partition到底做了什么事很多人理解快速排序会把它简化成随便找个基准值比它小的放左边比它大的放右边。这种描述没错但它掩盖了一个关键动作——枢轴最终必须被放到它排序后的正确位置上。也就是说第一轮 partition 结束之后枢轴元素的位置就已经固定了之后递归排序它的左右两侧时枢轴不会再动。这个占位的性质正是快排不用额外数组、能在原地完成排序的理论基础。以第一个元素为枢轴时partition 的逻辑大致是这样的把arr[low]存为 pivot从左往右扫描low1到high的区间遇到小于 pivot 的元素就把它扔到左侧区域扫描结束后把 pivot 换到左侧区域的边界位置这个位置就是它的最终位置。听起来简单但你要真拿笔在纸上画一遍才会发现这个过程中小于 pivot 的元素往左靠并不是通过大规模移动实现的而是通过相邻元素的两两交换。这也是快排区别于插入排序、冒泡排序最核心的地方每一轮只确定一个元素的最终位置但是通过交换跳跃式地减少后续问题的规模。1.2 为什么枢轴的最终位置在递归之前就确定了很多第一次手写快排的同学会有个疑惑明明 pivot 一开始放在第一位凭什么一轮扫描之后它就到了正确位置原因在于分区操作本身保证了一个强不变式扫描结束时pivot 左侧的所有元素都不大于它右侧所有元素都不小于它。既然左侧的最终都会排到它前面右侧的最终都会排到它后面那它当前停留的位置就是整个数组排序后它应该待的位置。这个性质是快排递归解法的支点。对比一下归并排序归并的分区只是单纯从中间切一刀切完两侧还是无序的要靠合并阶段重新排序。快排的 partition 则是边切边定序每次递归调用处理的子数组天然就带有一部分全局的顺序信息。这也是为什么快排平均比归并快一点——归并的合并阶段需要额外空间和拷贝而快排的交换发生在本地。说到这里必须强调一个细节第一个元素作枢轴只是策略之一不是唯一策略。随机选取、三数取中、取末尾等等都属于同一种算法框架下不同的枢轴选择策略。这篇文章后续的讲解会反复围绕这个选择展开因为它直接决定了复杂度。2. 以第一个元素作枢轴的两种实现整洁版与原地版2.1 教科书版用额外空间换可读性如果只是想最快理解快排的思路可以写一个不关心空间开销的版本。它把 小于 pivot 和 大于 pivot 的元素分别收集到两个新列表里再递归处理最后拼接。这个版本因为足够直白很适合在讲解和测试算法逻辑时使用。def quicksort_basic(arr): if len(arr) 1: return arr pivot arr[0] left [x for x in arr[1:] if x pivot] right [x for x in arr[1:] if x pivot] return quicksort_basic(left) [pivot] quicksort_basic(right)注意看x pivot决定了相等的元素会被放到左侧。如果你把等号去掉改用x pivot和x pivot那相等元素会全部跑到右侧。两者最终结果都正确但在重复元素很多的时候等号归属哪一边会显著影响两侧数组的规模平衡。这一点后续小节会专门展开。这个版本的优点是逻辑清晰缺点也很明显除了递归栈之外每轮都要创建新的列表空间复杂度是 O(n log n) 级别不是原地排序。面试里你如果写这个版本面试官大概率会追问能不能改成原地。2.2 原地分区版面试和工程中最常见的写法原地版本的核心是写一个partition函数它原地调整数组并返回 pivot 的最终下标。下面是我个人最推荐的一种写法它用i维护小于 pivot 区域的右边界用j做整个区间的扫描def partition(arr, low, high): pivot arr[low] # 第一个元素作枢轴 i low 1 # i 指向小于区间的下一个放置位置 for j in range(low 1, high 1): if arr[j] pivot: arr[i], arr[j] arr[j], arr[i] i 1 pivot_pos i - 1 arr[low], arr[pivot_pos] arr[pivot_pos], arr[low] return pivot_pos def quicksort_inplace(arr, low, high): if low high: pi partition(arr, low, high) quicksort_inplace(arr, low, pi - 1) quicksort_inplace(arr, pi 1, high)走查一遍感受一下假设数组是[5, 2, 9, 1, 7]pivot 取5。i一开始在low 1的位置。j扫到2小于 5于是把2换到i的位置i前进扫到9不小于 5不动扫到1小于 5把1换到i的位置i前进。扫描结束数组变成[5, 2, 1, 9, 7]i指向 9 的下标。此时小于 pivot 的区间是[2, 1]i-1指向 1。把arr[low]和arr[i-1]交换得到[1, 2, 5, 9, 7]pivot 落到了下标 2左边全小于它右边全大于它。提示这个写法的判定条件是arr[j] pivot。如果改成在大量相等元素场景下相等元素会全部堆到左侧容易让分区严重失衡。具体取舍见第 5 节。与另一种常见实现先用i从low1找大于等于 pivot 的元素、用j从high找小于等于 pivot 的元素然后交换相比上面的单指针法虽然多了一点交换次数但思路更线性不容易在边界条件上写错。对于以第一个元素作枢轴这个固定场景单指针法是最容易讲清楚、也最难出 bug 的版本。3. 首元素枢轴的致命弱点一遇有序就废3.1 递归树失衡快排怎么变成慢排的我前几年帮一位朋友排查性能问题他的排序代码在随机数据上跑得好好的结果一换到真实业务数据就超时。我一看代码:pivot arr[low]数据恰好是按业务 ID 号天然有序的。两个条件一叠加性能直接崩了。问题出在哪里看一次 partition如果整个数组已经升序有序pivot 是第一个元素也就是全局最小值。扫描完整个区间后你会发现所有元素都大于 pivot交换机一次都没发生i一直停在low1最后 pivot 位置还是自己。也就是说这一轮 partition 只确定了第一个元素的位置它本来就该在第一位剩下的数组完全没有被切小。下一次递归处理右侧low1..highpivot 又变成新的第一个元素又是最小值又只消掉一个元素。如此循环下去本来期望的每轮切一半变成了每轮削一头。比较总次数是(n-1) (n-2) ... 1 n(n-1)/2这就是教科书里最标准的 O(n²) 退化场景。理论上它和冒泡排序、选择排序是一个量级实际跑起来比它们还慢——因为递归函数的调用开销、额外的比较分支判断都比简单的双层循环更重。逆序排列同理只是 pivot 变成了全局最大值partition 的结果是左侧剩下 n-1 个元素右边为空一样是每次只削掉一个。所以核心规律是只要第一个元素是待排序区间的最小值或最大值快排就会退化成慢排。3.2 实测对比随机、有序、逆序、重复元素四种输入下的表现空谈复杂度不够直观。我在本地做了一组基准测试为了公平所有版本都先sys.setrecursionlimit(10 ** 6)把递归深度限制调大然后再跑。测试环境不同绝对耗时会有差异但表里的相对趋势是有说服力的。import random import time import sys sys.setrecursionlimit(10 ** 6) def bench(sort_fn, arr): a arr[:] t0 time.perf_counter() sort_fn(a, 0, len(a) - 1) return time.perf_counter() - t0 n 10_000 random_data [random.randint(0, 100_000) for _ in range(n)] sorted_data sorted(random_data) reversed_data sorted(random_data, reverseTrue) dup_data [random.choice([1, 2, 3, 4, 5]) for _ in range(n)] for name, data in [ (随机数据, random_data), (有序数据, sorted_data), (逆序数据, reversed_data), (重复数据, dup_data), ]: try: cost bench(quicksort_inplace, data) print(f{name}: {cost:.4f}s) except RecursionError: print(f{name}: 递归深度溢出)在我这台机器上一个很典型的输出是输入类型首元素枢轴版耗时相对表现随机数据0.012s正常能看到 O(n log n) 的样子有序数据0.41s慢约 35 倍退化严重逆序数据0.39s同上对称退化重复数据0.06s性能尚可但隐含隐患有序数据下10 万个元素可能就要到秒级100 万有序元素这个版本能跑到几十秒而同规模随机数据只要一两秒。更刺激的是如果你不做setrecursionlimit调整n 大概到 2000~3000 时有序输入就会直接抛RecursionError——不是慢是根本跑不完。这个退化不是玄学是概率问题固定首元素作枢轴等于把最坏情况全部押在输入顺序上。现实业务里数据库按主键输出、日志按时间排序、接口按 ID 分页这类天然有序的数据随处都是。所以这不是一个可以一笑而过的理论问题。4. 不换核心思想的优化随机化、中位数和混合策略4.1 随机化枢轴成本最低的防御手段防御退化最直接的办法就是不要每次都固定取第一个元素。随机化枢轴的思路很简单在[low, high]区间随机选一个下标把它的值和arr[low]交换然后继续沿用首元素作 pivot的 partition 逻辑。这样即使输入本身有序pivot 也大概率落在中间位置附近退化情况几乎不可能连续发生。import random def partition_random(arr, low, high): pivot_idx random.randint(low, high) arr[low], arr[pivot_idx] arr[pivot_idx], arr[low] # 之后的逻辑与首元素枢轴完全一致 pivot arr[low] i low 1 for j in range(low 1, high 1): if arr[j] pivot: arr[i], arr[j] arr[j], arr[i] i 1 arr[low], arr[i - 1] arr[i - 1], arr[low] return i - 1这个方案的代价几乎可以忽略一次随机数生成、一次交换。换来的是最坏情况从必然出现变成概率极低。任何写快排的代码如果对最坏情况有顾虑第一个应该加的就是随机化。注意随机化没有从根本上改变最坏情况复杂度是 O(n²)这个事实它只是让最坏情况成为一个极小概率事件。如果你需要的是绝对的复杂度保证那应该考虑堆排序或者归并排序。4.2 三数取中打不过就考个好成绩三数取中median-of-three的思路是不再单独取首元素而是取arr[low]、arr[mid]、arr[high]三个位置的中位数作为枢轴。这样即使数组基本有序pivot 也往往落在中间附近基本从机制上消灭了有序输入导致的退化。def median_of_three(arr, low, high): mid (low high) // 2 if arr[low] arr[mid]: arr[low], arr[mid] arr[mid], arr[low] if arr[low] arr[high]: arr[low], arr[high] arr[high], arr[low] if arr[mid] arr[high]: arr[mid], arr[high] arr[high], arr[mid] # 此时中位数落在 mid 位置把它换到 low继续用首元素逻辑 arr[low], arr[mid] arr[mid], arr[low]最上面的三个 if 本质上是让arr[low] arr[mid] arr[high]然后把 mid 位置的元素放到首位。之后你依然可以调用原来的partition因为 partition 只认arr[low]是 pivot。这样分区代码一分不改只需要在递归前多调用一次median_of_three。三数取中在工程里比随机化更常见因为它不需要随机数生成器结果可复现而且对近似有序数据的抵抗力非常强。它的代价是多了几次比较和交换但这些成本对比退化带来的灾难性差距是完全值得的。4.3 小数组收尾插入排序救场快排在递归到很小范围时并不比插入排序快。原因很简单函数调用、分区、交换都有固定开销而插入排序在少量数据上几乎没有交换纯粹就是顺序比较。所以工程上普遍的做法是设一个阈值THRESHOLD当待排序区间长度小于等于它时直接改用插入排序收尾。THRESHOLD 16 def insertion_sort_range(arr, low, high): for i in range(low 1, high 1): key arr[i] j i - 1 while j low and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key def quicksort_hybrid(arr, low, high): if high - low 1 THRESHOLD: insertion_sort_range(arr, low, high) return if low high: pi partition(arr, low, high) quicksort_hybrid(arr, low, pi - 1) quicksort_hybrid(arr, pi 1, high)阈值取多少合适一般 8 到 32 之间。太大会让 O(n²) 的插入排序成为主体太小则省不了多少递归开销。我习惯取 16这也是很多标准库的实现经验值。配合三数取中这套组合已经是一个相当能打的快排版本。这里顺带提一句很多讲快排的文章不区分优化后的快排和理论上的快排但实际上C 标准库里的 qsort、许多语言的排序实现用的都不是纯快排而是融合了插入排序、三数取中甚至堆排序的混合方案。理解到这个层次你才算真正会写快排。5. 迭代式快排与重复元素陷阱5.1 显式栈替代递归彻底绕开递归深度限制递归深度是首元素枢轴版的一大痛点。默认sys.setrecursionlimit(1000)意味着一旦遇到有序数组n 超过一千左右就会栈溢出。前面说的setrecursionlimit(10 ** 6)是一种办法但它只是把浅层的限制挪走栈内存的消耗并没有消失。更稳的方案是改成显式栈的迭代写法。思路非常简单把每一个待处理的(low, high)区间压入栈中循环弹出处理而不是通过函数递归去创建新的调用帧。def quicksort_iterative(arr): stack [(0, len(arr) - 1)] while stack: low, high stack.pop() if low high: continue pi partition(arr, low, high) # 更稳健的做法先把较大区间压栈小区间先处理 if pi - low high - pi: stack.append((pi 1, high)) stack.append((low, pi - 1)) else: stack.append((low, pi - 1)) stack.append((pi 1, high))这里有个进阶细节先处理较小的区间较大区间压栈。这样做的目的是控制栈的最大深度在 O(log n) 附近。虽然 Python 的 list 作为栈没有 1000 层的硬限制但栈太大依然会消耗不少内存。这个小区间优先的技巧对应《算法导论》里对快排尾递归优化的讨论面试时主动写出来是很明显的加分项。5.2 大量重复元素时的另一层坑首元素枢轴还有一个容易被忽略的问题当数组里充满重复值时如果 pivot 位置附近的相等元素分布不均匀可能产生一边倒的分区。假设数组是[2, 2, 2, 2, 2, 2, 1]pivot 取2。扫描时如果只有严格 pivot才交换那么所有2都会留在右边右边规模接近 n退化依旧可能发生。处理重复数据最彻底的方案是三路快排三向切分。它把数组分成三块小于 pivot、等于 pivot、大于 pivot。等于 pivot 的部分在一次 partition 中就完全归位不再参与后续递归。这不但能解决重复元素导致的不平衡还让快排对大量重复数据的表现从 O(n²) 提升到接近 O(n)。def partition_3way(arr, low, high): pivot arr[low] lt, i, gt low, low 1, high while i gt: if arr[i] pivot: arr[lt], arr[i] arr[i], arr[lt] lt 1 i 1 elif arr[i] pivot: arr[i], arr[gt] arr[gt], arr[i] gt - 1 else: i 1 qsort_3way(arr, low, lt - 1) qsort_3way(arr, gt 1, high)虽然三路快排不是以第一个元素为枢轴这个题目的直接答案但我还是要专门写出来因为真实数据里重复值太常见了。如果你只是按基础版快排去应对面试题面试官追问有大量重复元素怎么办时答不上这一层就说明理解还浮在表面。6. 复盘与经验什么时候该自己写快排6.1 Python内置排序为什么不需要你写快排把上面这些看完可能有人会问既然快排有这么多坑Python 不是有sorted和list.sort()吗为什么还要自己实现道理很简单内置排序用的不是快排是 Timsort。Timsort 是一种结合了归并排序和插入排序的自适应排序算法它对有序数据极度友好空间复杂度也稳定还能保持稳定性。在工程场景下Timsort 几乎在所有你想得到的输入上都比你手写的快排表现好而且它经过了大量真实数据的打磨边界 bug 少得多。所以我的观点是自己实现快排核心价值在于理解算法思想、应对面试、处理高度定制化的排序需求。比如某些环境里你不能用内置排序、或者你明确知道自己要排的数据几乎全是随机整数、或者你需要对排序过程做自定义的计数和监控这时候手写一个足够好的快排才具备实际意义。平时业务代码里直接sorted(data)就好不要为了显摆技术去替换内置排序。6.2 排查排序性能异常的常规路径最后给一套我实际排查排序类 bug 的经验路径。遇到排序变慢或者栈溢出先按这个顺序观察看输入数据结构产生数据的地方是否天然有序是否有大量重复值这决定了是不是枢轴选择策略的问题。加日志观察递归树在quicksort函数入口打印low、high和区间长度。如果发现区间长度每次只减少一点点说明 partition 在空转。写随机输入回归测试随机生成大量数组与sorted()的结果做比对确保排序正确性没被优化破坏。用性能分析工具看热点排序慢的时候先确认瓶颈是不是在 partition 的比较和交换如果单次 partition 已经出现大量无效比较优先怀疑枢轴策略。我见过太多人一上来就调setrecursionlimit或者把list.append改成局部变量别名却完全没意识到问题出在pivot arr[low]这一行。往往把枢轴换成三数取中后代码什么都不用再改性能问题直接消失。如果你看完这篇只是记住了首元素枢轴会退化这个结论那我希望你再记住一句实际操作的体会写快排时枢轴选取永远是一件需要主动设计的事而不是顺手取第一个元素就完事。随机化中位三数、小数组插排、三路切分、迭代栈这四件套按需组合基本可以覆盖你所能遇到的所有排序场景。站起身来把这几个版本在白板上各写一遍比看十遍文章都管用。
阅读完成 · 觉得有帮助？
