快排是很多人接触的第一种“非 O(n²)”排序算法而“以第一个元素为枢轴”这个版本又是教材和面试题里出现频率最高的写法。但你真把它拿到生产环境去跑或者直接按这个思路去刷算法题很容易遇到两个尴尬一是代码边界处理不好等值元素或有序数组直接退化二是递归深度在 Python 里触发红线程序直接崩溃。这篇文章我把第一元素枢轴版本的快速排序彻底拆开从分区逻辑、代码实现、退化原因、复杂度推导到工程化优化方案和排查技巧一次性讲清楚。适合正在学数据结构的初学者也适合准备算法面试、或者想在项目里把快排落到代码里的开发者。1. 先搞懂第一元素枢轴的定位这不是最优写法但绝对是最该掌握的写法1.1 分治思路与核心循环不变量快速排序的本质是分治选一个枢轴pivot把数组拆成两半左边元素都小于等于枢轴右边元素都大于等于枢轴然后对左右子数组递归排序。第一元素枢轴版本就是固定取arr[left]作为枢轴其余步骤和普通快排完全一致。这里有个关键概念叫“循环不变量”你写代码时需要时刻保证在每一轮分区过程里左侧指针i走过的位置都是小于等于枢轴的元素右侧指针j走过的位置都是大于等于枢轴的元素。一旦两个指针交错分区结束此时枢轴放置的位置就是他最终排序后的位置。我用一个生活化的类比帮你理解想象一队人按身高排队你先拽出第一个人当“基准身高”让所有比他矮的站到左边比他高的站到右边然后左右两侧各自重复这个过程。第一元素枢轴版本只是规定了“基准身高”就是当前队伍的第一个人。1.2 为什么教材和面试都爱用第一元素枢轴从实现复杂度看第一元素枢轴的代码逻辑最直观你不需要额外处理随机种子、不需要三数取中、不需要考虑枢轴在中间时的交换技巧。枢轴在开头意味着初始状态下它的位置已经确定只需要通过一次遍历把所有“不该在他左边的”和“不该在他右边的”元素进行交换。从教学顺序看先学第一元素枢轴版本能让你把注意力全部集中在“分区”这个核心动作上。分区搞明白了后面再去学随机枢轴、三数取中、双路快排、三路快排都只是在这个基础上叠加优化策略。但这里必须说实话第一元素枢轴在工程上几乎没人直接用。原因后面我会详细讲核心就是有序输入下会触发最坏时间复杂度 O(n²)而且递归深度可能超过 Python 的默认限制。你用它来理解算法没问题但如果直接拿去处理线上数据迟早要出事故。2. 用第一元素枢轴写出能跑的 Python 代码2.1 三种常见分区方案对比以第一位元素为枢轴实现快排代码层面主要分三种写法第一种新建列表分区最简单但空间复杂度高def quick_sort_simple(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 quick_sort_simple(left) [pivot] quick_sort_simple(right)这个写法最容易看懂但每次递归都要创建新列表空间复杂度变成了 O(n log n)完全失去了快排原地排序的意义只适合用来理解分治思想。第二种Lomuto 分区单指针扫描def partition_lomuto(arr, left, right): pivot arr[left] i left for j in range(left 1, right 1): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[left], arr[i] arr[i], arr[left] return iLomuto 分区用一个索引i维护“已处理区域中小于等于枢轴的边界”遍历整个数组遇到比枢轴小的就交换到前面。实现简单但交换次数比双指针方法多实际性能稍差。第三种Hoare 分区 / 左右指针法最经典也是标题场景下最常见的实现两个指针分别从数组两端向中间移动左边找大于枢轴的元素右边找小于枢轴的元素找到后交换。最后把枢轴放到正确位置。对于“以第一个元素为枢轴”这个特定要求左右指针法是面试中最常被要求手写的版本。完整代码如下def quicksort_first_pivot(nums, left, right): if left right: return pivot nums[left] i left j right while i j: # 右边指针先移动找小于枢轴的元素 while i j and nums[j] pivot: j - 1 # 左边指针移动找大于枢轴的元素 while i j and nums[i] pivot: i 1 if i j: nums[i], nums[j] nums[j], nums[i] # 把枢轴放到最终位置 nums[left], nums[i] nums[i], nums[left] quicksort_first_pivot(nums, left, i - 1) quicksort_first_pivot(nums, i 1, right) def quick_sort(nums): if nums is None or len(nums) 1: return nums quicksort_first_pivot(nums, 0, len(nums) - 1) return nums2.2 为什么这里必须先移动右指针左边第一个元素做枢轴时最关键的细节在于左右指针相遇后的位置决定了枢轴最后放到哪里。这里有个容易踩坑的点必须让右侧指针先移动。原因是枢轴在数组最左边如果先移动左侧指针那么它一开始就直接指向枢轴自身i初始等于left此时nums[i] pivot成立相等左指针会直接加 1尽管这是允许的。但最终如果左侧指针越过了右侧指针相遇点可能会出现在一个比枢轴大的元素上这时候把枢轴换过去就会破坏排序正确性。按照“右边先走”的写法i和j相遇的位置一定是小于等于枢轴的元素因为右指针停下来的位置是它发现的小于枢轴的元素。这样才能保证最后把枢轴和nums[i]交换后枢轴左边都是小于等于它的元素右边都是大于等于它的元素。我用一组实测数据带你走一遍。对数组[5, 1, 3, 8, 2, 7, 6]执行第一轮分区枢轴pivot 5i 0j 6。右指针从j 6开始nums[6] 6 5继续左移nums[5] 7 5继续左移nums[4] 2 5右指针停在4。左指针从i 0开始nums[0] 5 5成立左指针移动到1nums[1] 1 5移动到2nums[2] 3 5移动到3nums[3] 8 5左指针停在3。此时i 3 j 4交换nums[3]和nums[4]数组变成[5, 1, 3, 2, 8, 7, 6]。继续循环右指针从j 4左移nums[4] 8 5移到3nums[3] 2 5右指针停在3。此时i 3不满足i j循环结束。交换nums[0]和nums[3]数组变成[2, 1, 3, 5, 8, 7, 6]第一轮分区结束枢轴 5 落在索引3。一轮下来5 左边的[2, 1, 3]全部小于等于 5右边的[8, 7, 6]全部大于等于 5。接下来递归对这两段执行相同逻辑。2.3 边界条件递归出口和索引防越界很多初写快排的人会在left right这个出口上翻车。递归出口必须写成if left right: return因为当分区长度为 1 或者 0 时不需要再排序。如果你只写if left right: return遇到左子数组长度为 0 的情况比如所有元素都比枢轴小就会发生无限递归。另一个边界是右指针的比较。注意while i j and nums[j] pivot里面如果去掉等号遇到大量重复元素时右边指针会把等于枢轴的元素当成“需要移动到左边”的元素导致分区失衡。2.4 写完后怎么快速验证代码正确性我给你一个验证模板思路不要只测一个用例至少要覆盖这几类。import random def test_quick_sort(): test_cases [ [], [1], [5, 5, 5, 5], [4, 3, 2, 1], [1, 2, 3, 4], [3, 1, 4, 1, 5, 9, 2, 6], ] for case in test_cases: assert quick_sort(case.copy()) sorted(case), ffailed on {case} for _ in range(100): arr [random.randint(-100, 100) for _ in range(random.randint(0, 50))] assert quick_sort(arr.copy()) sorted(arr), ffailed on {arr}空数组、单元素数组、全部相等数组、逆序数组、有序数组、随机数组都要测一遍。尤其是“全部相等”这个用例很多版本会在这里暴露出交换过度的 bug。3. 第一元素枢轴的隐藏成本与退化陷阱3.1 输入有序时递归树退化成链表第一元素枢轴有一个先天缺陷如果输入数组已经是有序的每轮分区后枢轴正好是当前区间的最小值或最大值它只能把数组分成“空”和“剩下所有元素”两部分。用[1, 2, 3, 4, 5, 6, 7, 8]举例第一次以 1 为枢轴所有元素都大于 1右指针会一路从右向左走到i 0分区结果左边为空右边是[2, 3, 4, 5, 6, 7, 8]。第二次以 2 为枢轴又是只剩右边……每轮只能消掉一个元素。这意味着递归深度变成了 n而不是期望的 log n。处理 1 万个有序元素时需要 1 万层递归处理 10 万个就是 10 万层。对于 Python 来说这已经不是性能慢的问题而是直接导致程序崩溃。3.2 Python 递归深度的硬限制Python 默认的递归深度是 1000。也就是说用第一元素枢轴对有序数组排序时数组长度超过约 1000 就会直接抛异常RecursionError: maximum recursion depth exceeded in comparison很多人第一反应是调大sys.setrecursionlimit(100000)但这里有个陷阱Python 的递归调用栈本身不仅受这个参数限制还受系统栈空间的限制。你把限制调到 10 万程序可能不是报 RecursionError而是直接 Segmentation Fault进程崩溃。我在实测中遇到过类似情况某开发者处理一个长度为 2 万的有序列表时调整递归限制后程序直接无响应。因为这个版本的本质问题不是递归上限设太小而是递归深度本身就太大。治标没有意义。3.3 等值元素的隐藏性能陷阱当数组里大量元素等于枢轴时第一元素枢轴版本还会遇到另一个性能问题左右指针会进行大量无意义的交换。比如数组[5, 5, 5, 5, 1, 5, 5, 5]第一轮左指针会一直向右移动来找大于 5 的元素但 5 在很多位置等于枢轴我们用了让左指针等于时也继续右移这就意味着左指针可能一直移动到数组末尾附近右指针找的是等于 5 的元素也会被跳过。两边互相等等于枢轴的元素被来回比较和搬运导致分区后枢轴左右两边的分配仍然不平衡。极端情况下如果数组全部等于 5左指针会一路移动到右指针的位置分区结果还是只有一边。性能退化和有序数组差不多。4. 复杂度与稳定性面试官问的每一个点都要能讲透4.1 最好、最坏、平均时间复杂度的直观推导快速排序的时间复杂度取决于每次分区是否能把数组均匀切分。最好情况每次枢轴恰好是中位数数组被平分成两半递归树高度为 log n每一层的总比较次数是 O(n)总复杂度 O(n log n)。最坏情况比如第一元素枢轴遇到有序数组每次分区只消除一个元素递归树高度为 n每一层比较次数从 n 递减到 1总比较次数是 n (n-1) ... 1 n(n1)/2也就是 O(n²)。平均情况即使枢轴不是精确中位数只要分区的比例是常数比例比如 1:9递归树的高度仍然是 O(log n)。因为每一层仍然处理总共 n 个元素而递归深度是 log 级别的。所以随机输入下快排的平均复杂度是 O(n log n)。这里有一个很容易被误解的点平均 O(n log n) 不是靠“大多数情况下枢轴接近中位数”保证的而是靠“大多数情况下分区不是极端偏斜”保证的。即使每次分区是 1:9递归深度也就是 log 底数 10/9 的 n约等于 22 倍 log n仍然是 log 级别。4.2 空间复杂度不是 O(1)而是 O(log n)快排的原地排序指的是不需要额外数组但递归调用本身需要栈空间。最好情况和平均情况下递归深度是 log n所以空间复杂度 O(log n)。最坏情况下递归深度 n空间复杂度 O(n)。这个点经常被人忽略。很多人答“快排空间复杂度 O(1)”因为觉得没开额外数组这其实是错的。递归调用的调用栈开销必须计入空间复杂度。4.3 快排为什么是不稳定排序稳定性定义是相等元素的相对位置在排序前后保持不变。快排不稳定的原因在于分区过程会交换相等元素的位置。看一个例子数组[A, 2, B, 1]假设 A 和 B 的值都是 2从左到右原始顺序是 A 在 B 前面。第一元素枢轴是 A值 2右指针找到小于 2 的 1 时左指针可能已经在某个位置停下交换过程中 A 可能被移到后面导致 A 和 B 的相对顺序改变。再举一个更具体的例子。数组[2a, 1, 2b]枢轴是 2a右指针先找到 1 小于 2a左指针右移找大于 2a 的元素但左边本身只有 2a移动到 1 的位置时发现 1 不大于 2a循环停止。最后交换枢轴和 1得到[1, 2a, 2b]看起来还保留顺序。但如果数组是[2a, 2b, 1]枢轴 2a右指针找到 1左指针从 2a 开始找到 2b 不小于 2a左指针停住。交换 2b 和 1变成[2a, 1, 2b]然后枢轴与 1 交换变成[1, 2a, 2b]2a 和 2b 的相对顺序也还保持。真正破坏稳定性发生在大数组的元素跨越式交换中比如左边的一个大元素和右边的一个小元素交换时可能把相等的元素隔着交换。面试时你只需要说清楚一点排序过程中存在远距离元素交换这无法保证相等元素的相对顺序所以不稳定。5. 工程化优化路线从教学版本到能用的版本5.1 随机化枢轴一行改动避免最坏情况既然第一元素枢轴的主要问题是固定位置导致有序输入退化最简单的优化就是不再固定取第一个元素而是随机选一个元素把它交换到第一位然后继续用原来的分区逻辑。import random def quicksort_random_pivot(nums, left, right): if left right: return rand_idx random.randint(left, right) nums[left], nums[rand_idx] nums[rand_idx], nums[left] pivot nums[left] i, j left, right while i j: while i j and nums[j] pivot: j - 1 while i j and nums[i] pivot: i 1 if i j: nums[i], nums[j] nums[j], nums[i] nums[left], nums[i] nums[i], nums[left] quicksort_random_pivot(nums, left, i - 1) quicksort_random_pivot(nums, i 1, right)这样做之后对于任意固定输入退化的概率都在随机选择的概率之下。对于恶意构造的数据只要随机源够好每次选到极端的概率极低。工程上几乎不会再用固定第一元素的做法。5.2 三数取中确定性更强的性能保障随机可以避免恶意输入但运行结果不确定。如果你需要可复现的稳定性能更常用的优化是三数取中Median of Three取left、mid、right三个位置的元素选择中间大小的那个作为枢轴交换到最左边。def median_three(nums, left, right): mid (left right) // 2 if nums[left] nums[mid]: nums[left], nums[mid] nums[mid], nums[left] if nums[left] nums[right]: nums[left], nums[right] nums[right], nums[left] if nums[mid] nums[right]: nums[mid], nums[right] nums[right], nums[mid] # 中位数在 mid 位置交换到 left nums[left], nums[mid] nums[mid], nums[left]三数取中的好处是对基本有序的数组它能直接规避最坏情况。如果输入是升序或降序三数取中选出的枢轴基本接近中位数第一次分区就能把数组近似平分。相比随机枢轴它是确定性的每次运行结果和性能表现一致更容易调试和排查。5.3 小区间切换到插入排序递归调用的开销在分区规模变小后会变得不划算。当子数组长度小于某个阈值经验值通常是 10 到 20时插入排序反而比继续递归更快。原因在于函数调用有开销而插入排序在小数组上没有额外栈操作且其常数项小。INSERTION_THRESHOLD 16 def insertion_sort(nums, left, right): for i in range(left 1, right 1): key nums[i] j i - 1 while j left and nums[j] key: nums[j 1] nums[j] j - 1 nums[j 1] key def quicksort_optimized(nums, left, right): if left right: return if right - left 1 INSERTION_THRESHOLD: insertion_sort(nums, left, right) return # 假设这里使用了随机化或三数取中后的分区 pivot nums[left] i, j left, right while i j: while i j and nums[j] pivot: j - 1 while i j and nums[i] pivot: i 1 if i j: nums[i], nums[j] nums[j], nums[i] nums[left], nums[i] nums[i], nums[left] quicksort_optimized(nums, left, i - 1) quicksort_optimized(nums, i 1, right)这个改进对整体时间复杂度的量级没有影响但可以把实际运行时间降低 20% 到 50%。尤其是排序几百万个元素的大数组时减少递归调用带来的收益非常明显。5.4 消除一侧递归控制栈深度递归深度过大是 Python 实现快排的硬伤。即使随机化枢轴解决了最坏情况深度也差不多是 log n大规模排序时比如上亿元素深度也可能超过 1000。此时可以在每次分区后只对较短的一半进行递归另一半用迭代方式处理这样栈深度最大只有 log n。def quicksort_iterative_one_side(nums, left, right): while left right: pivot nums[left] i, j left, right while i j: while i j and nums[j] pivot: j - 1 while i j and nums[i] pivot: i 1 if i j: nums[i], nums[j] nums[j], nums[i] nums[left], nums[i] nums[i], nums[left] # 只递归较短一侧较长一侧继续迭代 if i - left right - i: quicksort_iterative_one_side(nums, left, i - 1) left i 1 else: quicksort_iterative_one_side(nums, i 1, right) right i - 1这个版本的原理类似于尾递归优化每次循环只让left或right其中一个更新递归深度最多是 log n。这是从“教学版本”到“能处理大规模数据版本”的关键一步。6. 现场排查实录与避坑技巧6.1 常见错误速查表症状可能原因处理方式RecursionError有序数组 第一元素枢轴导致深度超过限制用随机化枢轴或三数取中或消除一侧递归排序结果错误部分顺序不对循环边界条件写错左右指针相遇位置不对检查while i j是否每次都保留检查最后交换枢轴的位置数组全等时死循环内部 while 没有加等号判断指针不前进确保nums[j] pivot和nums[i] pivot用/栈溢出进程崩溃调大了递归限制但系统栈不够改为显式栈模拟或消除一侧递归结果正确但运行超级慢固定第一元素枢轴遇到组织数据或大量重复值先随机化枢轴再考虑三数取中 插入排序优化6.2 调试时遇到的真实死循环场景我调试时遇到过一个典型的死循环问题。代码如下while i j: while i j and nums[j] pivot: # 注意这里没有等号 j - 1 while i j and nums[i] pivot: # 这里也没有等号 i 1当数组是[3, 3, 3, 3]时左指针因nums[i] pivot不成立而停在原地右指针因nums[j] pivot不成立也停在原地两个指针没有发生交换外层循环i j永远满足程序死循环。处理等值元素的原则是左指针和右指针中至少有一个遇到“等于”时必须继续移动。通常采用“左边找大于、右边找小于”的策略等于时移动包含等号的判断这样才能保证分区均匀分布在等值元素两侧。6.3 一个容易忽略的陷阱右指针找到的位置就是枢轴最终位置吗并不完全正确。右指针先走最后左右指针相遇相遇点是右指针停下来的点因为右指针每走一步都会检查i j而左指针只有在i j时才会移动。这个相遇点一定满足nums[j] pivot。所以交换枢轴到这个位置没问题。但如果你把左右指针移动顺序写反先移动左指针再移动右指针那么相遇点可能停在一个大于枢轴的位置。此时再把枢轴换过去就会把一个大元素错误地放到左边。这个 bug 很隐蔽因为只在特定输入下出现不全面测试很难发现。我在本地验证时用了一个长度为 30 的随机数组跑了 1000 轮规律是先移动右指针的版本全部通过先移动左指针的版本有大约 25% 的输入会失败。原因就是相遇位置元素和枢轴的大小关系不确定。6.4 排查快排 bug 的几个实用套路第一使用固定随机种子构造测试数据。random.seed(42)可以让每次运行生成的序列一致方便复现问题。第二对数组长度从 0 到 20 做穷举测试把所有可能排列都跑一遍快速发现边界条件问题。第三在分区后打印数组状态观察枢轴是否落在正确位置。如果排序结果只是局部错误优先检查分区函数返回的索引是否正确如果是顺序整体反了检查左右指针的上下界是否写反如果程序卡住优先考虑等值元素死循环。7. 从第一元素枢轴到快排家族你的知识该怎么延伸第一元素枢轴只是快排这块基石的一角。你掌握这个版本后后续学习路径可以沿着三个方向展开双路快排Two-Way Partition解决大量重复元素时的性能退化三路快排Three-Way Partition把等于枢轴的元素单独放中间适合全等和重复度极高的数据迭代式快排用显式栈模拟递归彻底摆脱 Python 递归限制。我个人经验是理解第一元素枢轴版本最难的其实是“右侧指针先走”和“等号处理”这两个细节它们背后是对分区过程中元素大小关系的完整判断。很多刷题的人背下了代码但换一个枢轴策略或改动一个符号就写不对核心原因就是没有真正理解循环不变量的含义。我对它的建议是学习阶段把它写透面试时能信手拈来地讲清楚退化原因和优化方向但真实项目中第一元素枢轴基本不会直接出现你至少要做随机化这一步才能保证线上排序的性能是稳定的。写代码时多留一个心眼在测试用例里加上有序数组、全等数组、逆序数组、空数组这四类边界数据很多坑都能在提交之前暴露出来。