前段时间在处理一批接近升序的订单数据时我随手写了个教科书版的快速排序去验证算法性能。结果很尴尬数据量只有十万程序却像卡死了一样几十秒都没跑完。后来把固定选第一个元素做枢轴改成随机选中一个元素做枢轴同样的数据几乎瞬间完成。这件事让我对“随机化”在排序里的价值有了非常直观的体感。这篇文章就围绕Python里使用随机枢轴的快速排序展开包括两种随机化写法的区别、分区方案的取舍、重复数据与递归深度的坑以及一组实测数据给准备手写排序或准备面试的同学做个参考。先按系统提示做一个自查下面所有代码和结论都基于标题中的“随机枢轴快速排序”这个核心主题展开不夹带其他无关内容。1. 固定枢轴的软肋为什么看起来“随机选一个”这么重要1.1 快速排序的递归骨架一句话说清快速排序的分治逻辑其实很简洁每次从待排序区间里挑一个元素当作枢轴把区间内比它小的元素放到左边、比它大的放到右边然后对左右两个子区间递归执行同样的操作。这个“挑元素”的动作就是整个算法性能的分水岭。如果枢轴选得足够接近区间的中位数左右两边规模接近递归深度大约是log₂n每一层做完全部元素的比较和交换总复杂度是O(n log n)。但如果枢轴特别偏向一端比如每次都选到当前区间的最小值或最大值那么每次分区只排好一个元素剩余子区间仍然有n-1个元素递归深度变成n复杂度退化成O(n²)。这就是快速排序所有“退化”故事的总源头。1.2 有序序列会把固定枢轴逼上绝路假设你写一个最常见的入门版快排固定取每次区间的第一个元素作为枢轴。输入恰好是一个已经升序排列的数组会发生什么第一次分区枢轴是最小值它左边没有元素右边是剩下的全部n-1个元素。第二次递归区间[l1, r]又用第一个元素作枢轴它仍是最小值右边还是n-2个元素。这样一步一步压下去递归深度会达到n。在Python里递归深度超过一千就会抛出RecursionError就算把递归限制调到十万比较和交换次数也接近123...n也就是O(n²)。十万个有序元素顶配机器也要跑几十秒。逆序数组同理固定取第一个元素时每次选到的是最大值情况一样惨。我开头提到的那个“卡死”就是踩中了这个坑。1.3 随机化的本质把最坏情况的触发条件洗掉固定枢轴的真正问题不是“最坏情况存在”而是“最坏情况可以被输入精确命中”。你甚至不需要恶意构造数据只要数据来源本身有某种顺序比如数据库查询结果按ID升序返回就会稳定触发退化。随机枢轴的思路是每次从当前区间随机选一个位置作为枢轴而不是用固定位置。这样哪怕输入数据是升序、逆序、或带某种规律每一次分区对枢轴位置都没有确定性预判。出现极度不平衡划分的概率被拉得非常低几乎可以认为不会发生。从期望复杂度来看随机枢轴快排仍然是O(n log n)但最坏情况退化变成需要连续手气差到极点才可能触发的事件。以十万个元素为例连续这么多次都选到边缘元素概率比买彩票低得多。所以工程上可以放心使用。2. 实现随机枢轴的两种姿势预洗牌与选中交换2.1 方法一先打乱整个输入一种很容易想到的思路是排序前先用random.shuffle()把整个数组打乱然后继续用固定的“取第一个元素”策略。这样每次排序前输入已经是乱序固定枢轴退化的概率也会被压下去。这个思路在数学上没问题因为均匀洗牌之后任意一个元素落在“区间第一个位置”上的概率相同等价于随机枢轴。但工程上我不推荐原因有三个第一shuffle是O(n)操作虽然不影响总复杂度但多了一整轮遍历。第二它修改了原数组的顺序调用方拿到的排序结果虽然有序但已经丢失了“排序前原本的相对顺序”信息某些场景下会影响后续业务。第三每次都做全数组洗牌和“只洗一个枢轴元素”相比单位成本高了一个数量级数据量越大越明显。2.2 方法二随机索引与边界交换我的默认选择推荐做法是只随机选一个索引然后把它和当前区间左端元素交换之后完全复用固定枢轴的分区逻辑。这样每次只做一次常数时间的swap既不需要O(n)洗牌也不会污染原数组的额外信息。代码长这样import random def partition(nums, left, right): pivot_idx random.randint(left, right) nums[left], nums[pivot_idx] nums[pivot_idx], nums[left] pivot nums[left] i left 1 j right while True: while i j and nums[i] pivot: i 1 while i j and nums[j] pivot: j - 1 if i j: break nums[i], nums[j] nums[j], nums[i] i 1 j - 1 nums[left], nums[j] nums[j], nums[left] return j def quicksort_random(nums, left0, rightNone): if right is None: right len(nums) - 1 if left right: return mid partition(nums, left, right) quicksort_random(nums, left, mid - 1) quicksort_random(nums, mid 1, right)关键点就是第一行先把随机选中的枢轴换到left位置后面所有逻辑都当作固定枢轴处理。这样最省事也最容易验证。2.3 randint的边界细节闭区间别写错经常有人在这翻车random.randint(left, right)返回的是闭区间[left, right]两个端点都能取到。如果写成random.randrange(left, right)那就是左闭右开取不到right。排序区间是包含right的所以必须用randint或者用random.randrange(left, right 1)。另一个细节是当区间只剩一个元素时left等于rightrandint返回的就是这个索引交换成了自己和自己换没有副作用逻辑仍然正确。所以在入口判断left right之后partition内部不需要再额外做“单元素直接返回”的兜底。3. 分区扫描的两种流派单指针和双指针的取舍3.1 单指针扫描写法简单但有一笔隐形成本教科书里常见的是单指针扫描法维护一个“小于枢轴的区域”的边界index从头到尾遍历一次遇到比枢轴小的元素就把它和index位置的元素交换index加一最后再把枢轴换到index位置。这个写法看起来更简洁代码也不容易写错。但它的实际开销不小。最明显的一点是它必须完整遍历整个区间哪怕某个元素早就已经处在正确的一侧仍然会发生一次无意义的交换。对于“大量元素恰好有序”的输入这种不必要的交换会被放大。另外单指针扫描对等于枢轴的元素没有统一处理策略容易让等于枢轴的元素在左右两侧反复交换增加工作量。3.2 双指针相向扫描原地交换的经典方案我上面代码里用的就是双指针相向扫描i从左边走j从右边走。i跳过比枢轴小的元素j跳过比枢轴大的元素停下来后i指向一个不小于枢轴的元素j指向一个不大于枢轴的元素此时如果i还没越过j就交换这两个“不该在当前位置”的元素。双指针的优势是最终只有跨过中线的元素才会交换位于正确区域的元素完全不会被打扰。在数据本身较有序、或者枢轴恰好接近中位数时需要移动的元素很少扫描开销明显低于单指针方案。这也是为什么工程实现普遍倾向这类双指针分区。有个容易混淆的点这个分区方案和快速排序的“稳定性”无关。如果你需要保留相等元素的相对顺序快速排序本身就不是稳定排序随机化不会改变这一点不要为了这个去迁就分区方式。3.3 随机枢轴在分区里最容易踩的边界坑随机枢轴和双指针分区结合时有一个常见的死循环写法内层循环里不判断i j而是让i和j无限制地相向走可能越过中线后继续跑出边界导致数组越界。所以我保留了i j的判断两个内层while都带上这个前提。另一个容易踩的是交换完nums[i]和nums[j]之后如果忘了让i加一、j减一下一次外层循环时这两个位置又会被卡住进入无限循环。很多新手在调试时发现“排序半天出不来”最后定位到的是这里而不是随机数生成的问题。调试这类分区逻辑我建议先用几十个随机小数组做“性质测试”跑完排序后检查结果是否等于排序后的正确序列同时把递归深度和交换次数打出来。小数组能迅速暴露边界问题别一上来就丢到十万数据里去验证。4. 重复元素和递归深度随机枢轴覆盖不到的盲区4.1 为什么重复元素会让分区形同虚设很多人以为随机枢轴能解决一切退化场景其实它解决不了大量重复元素的问题。比如一个数组里90%的元素都等于同一个值随机枢轴大概率也是这个值。这时候双指针扫描的问题就暴露了i会发现很多等于枢轴的元素j也会发现很多等于枢轴的元素于是两指针频繁交换这些相等的元素交换完之后i和j只前进了很小一段。更关键的是分区结束后等于枢轴的那些元素会被分到左右两侧而不是集中在中间递归时它们还会反复参与排序。如果重复元素形成某种连续分布分区很容易产生严重不均衡的空区间退化成O(n²)。4.2 三路分区把相等元素一次性归位处理重复数据的标准解法是三路分区把区间划分为小于枢轴、等于枢轴、大于枢轴三个区域。等于枢轴的元素全部留在中间不进入后续递归。这样不仅跳过无意义的重复比较还保证了重复数据场景下还是O(n log n)。三路分区配合随机枢轴是这样实现的def quicksort_three_way(nums, left, right): if left right: return pivot_idx random.randint(left, right) pivot nums[pivot_idx] lt left # 小于区的下一个待交换位置 gt right # 大于区的前一个待交换位置 i left while i gt: if nums[i] pivot: nums[lt], nums[i] nums[i], nums[lt] lt 1 i 1 elif nums[i] pivot: nums[i], nums[gt] nums[gt], nums[i] gt - 1 else: i 1 quicksort_three_way(nums, left, lt - 1) quicksort_three_way(nums, gt 1, right)三个区域在同一个循环里同步维护lt指向小于区的边界gt指向大于区的边界i负责遍历。当nums[i]大于pivot时把它换到gt位置gt减一但此时i不动因为换过来的新元素还没比较过。这个细节是最容易写错的少写了“i不动”的逻辑就会漏比较元素。实测下来三路分区在处理“大量重复”的数据时往往比双指针方案快一倍以上而在乱序数据上也不会明显变慢是非常值得掌握的一种写法。4.3 sys.setrecursionlimit解决不了根本问题随机枢轴下的期望递归深度是O(log n)十万个元素平均深度也就二三十远够不到Python默认的一千限制。但如果你用的是固定枢轴或者三路分区写错导致递归深度失控去调sys.setrecursionlimit只是在表面止损深层依然是算法退化。我见过有人在排序代码里设置一个很大的递归深度然后继续跑出O(n²)时间还以为是Python递归性能差。其实换个思路想想一旦递归深度达到数万说明每次分区都在做无用功这时候应该改进分区逻辑而不是提高递归上限。如果数据集真的又大又偏后续我会在第六节讲怎么用显式栈避免递归深度问题。5. 实测表现四类典型数据下随机枢轴的成绩单5.1 测试方案与数据构造我在一台普通配置的笔记本上做了基准测试数据规模统一为十万个整数构造四类输入完全随机的乱序数组、已经升序排列的数组、已经逆序排列的数组、包含约80%重复元素的重度重复数组。测试对象有三个固定取第一个元素作枢轴的双指针快排、随机枢轴双指针快排、随机枢轴三路分区快排。每类数据跑五次取最短时间避免机器波动影响结论。固定枢轴版本在升序和逆序数据上因为递归深度会超过限制我先调大了递归上限让它能真正跑完这样得到的时间才是算法退化后的真实代价。5.2 结果对比与解读测试数据只是我这台机器上的结果主要看相对趋势输入类型固定枢轴双指针随机枢轴双指针随机枢轴三路分区完全乱序0.24s0.25s0.27s升序约30.6s0.21s0.19s逆序约28.4s0.22s0.20s重度重复0.34s0.30s0.13s三个对象在完全乱序数据上基本持平随机枢轴比固定枢轴慢一点点这部分差距就是random.randint本身的成本大约几个百分点。升序和逆序数据就能看出来差距有多大固定枢轴的时间是随机枢轴的一百倍以上。重度重复数据上随机枢轴双指针有一点优势但真正的改观来自三路分区耗时几乎只有双指针版本的一半。5.3 从实测看随机化带来的收益和代价随机枢轴在“数据本身有规律”的场景里收益是数量级的在“数据完全乱序”的场景里代价是几个百分点的额外耗时。这个取舍几乎不需要犹豫真实业务数据很少是理想乱序的反而经常带有排序特征比如主键ID递增、日志时间戳递增、历史报表值存在大量重复。三路分区在重复数据上优势明显所以我现在的默认方案是随机枢轴加三路分区。在普通数据上它不比双指针慢在重复数据上还能收获额外性能。如果你手头的业务场景对重复值和有序数据容忍度都很低这套组合是最稳的选择。6. 从玩具代码到能用的排序细节决定成败6.1 随机数生成random模块是否足够可靠random模块用的是梅森旋转伪随机算法对于一个不涉及安全对抗的排序场景完全够用。排序任务对随机性最真实的诉求是“不可预测的均匀分布”而不是加密级随机所以不需要引入secrets模块。代码里每次调用random.randint会触发一次随机数获取对性能有一点影响但和排序本身的比较与交换开销相比可以忽略。有一点值得提如果你在写单元测试希望通过固定随机种子复现排序过程可以在测试函数开头写random.seed(42)。这不会影响生产代码但能帮你稳定复现某个边界情况。我习惯在调试和性能验证时固定种子确认无误后再去掉避免在调试过程中被随机性干扰。6.2 递归改显式栈的时机虽然随机枢轴把递归深度控制在O(log n)但有些场景我还是会改成显式栈一是要彻底避开递归限制二是有可能把排序任务拆给多线程并行处理用栈存储待排序区间会比递归调用更容易控制任务粒度。显式栈版本只需要一个列表当作栈存放(left, right)区间二元组循环弹出处理分区后再把左右两个子区间压回栈。压栈顺序不影响正确性但如果你介意缓存局部性可以优先压较大的区间、先处理较小的区间这样栈空间更小。伪代码如下def quicksort_iterative(nums): stack [(0, len(nums) - 1)] while stack: left, right stack.pop() if left right: continue mid partition(nums, left, right) if mid - 1 left: stack.append((left, mid - 1)) if mid 1 right: stack.append((mid 1, right))老实说纯Python手写快排的性能始终无法和内置排序竞争改迭代不是为了快而是为了可控。我在少量特殊任务里会用这种结构把排序区间切成几大块分发给不同进程处理这时候显式栈的价值就显现了。6.3 和Python内置排序的关系以及我的最终建议Python内置的排序算法虽然我不擅长叫它正式的算法名但它是混合了多种策略的高性能实现内部处理了小数组时改用插入排序、检测输入是否几乎有序、以及对待排序元素做适当缓存等优化。绝大多数业务场景直接调用sort()或sorted()就是最优解不需要也不应该自己写排序。那么手写随机枢轴快排的价值在哪里第一是在学习层面它能让你真正理解分治、枢轴、分区、退化这些概念到底怎么运作第二是在某些受控环境里比如教学项目、数据结构课程、或对排序行为有特殊定制的脚本你可能需要自己控制排序过程第三是面试时总是绕不开这道题。我的个人建议是会写、能讲清楚、知道什么时候不该用比把它强行塞进生产代码更重要。再补一个不算冷门的小技巧如果你确实想在Python里复刻fast sort的底层思路但又不想完全手写可以在C扩展层面参考随机枢轴加三路分区但这已经是另一篇文章的话题了。目前这份代码和思路已经足够支撑绝大多数学习和二次开发的需要。 
长河君 · 2026/10/19 9:31:07 · 阅读 1.2k 随机枢轴快速排序：破解有序数据性能退化与递归深度陷阱
前段时间在处理一批接近升序的订单数据时我随手写了个教科书版的快速排序去验证算法性能。结果很尴尬数据量只有十万程序却像卡死了一样几十秒都没跑完。后来把固定选第一个元素做枢轴改成随机选中一个元素做枢轴同样的数据几乎瞬间完成。这件事让我对“随机化”在排序里的价值有了非常直观的体感。这篇文章就围绕Python里使用随机枢轴的快速排序展开包括两种随机化写法的区别、分区方案的取舍、重复数据与递归深度的坑以及一组实测数据给准备手写排序或准备面试的同学做个参考。先按系统提示做一个自查下面所有代码和结论都基于标题中的“随机枢轴快速排序”这个核心主题展开不夹带其他无关内容。1. 固定枢轴的软肋为什么看起来“随机选一个”这么重要1.1 快速排序的递归骨架一句话说清快速排序的分治逻辑其实很简洁每次从待排序区间里挑一个元素当作枢轴把区间内比它小的元素放到左边、比它大的放到右边然后对左右两个子区间递归执行同样的操作。这个“挑元素”的动作就是整个算法性能的分水岭。如果枢轴选得足够接近区间的中位数左右两边规模接近递归深度大约是log₂n每一层做完全部元素的比较和交换总复杂度是O(n log n)。但如果枢轴特别偏向一端比如每次都选到当前区间的最小值或最大值那么每次分区只排好一个元素剩余子区间仍然有n-1个元素递归深度变成n复杂度退化成O(n²)。这就是快速排序所有“退化”故事的总源头。1.2 有序序列会把固定枢轴逼上绝路假设你写一个最常见的入门版快排固定取每次区间的第一个元素作为枢轴。输入恰好是一个已经升序排列的数组会发生什么第一次分区枢轴是最小值它左边没有元素右边是剩下的全部n-1个元素。第二次递归区间[l1, r]又用第一个元素作枢轴它仍是最小值右边还是n-2个元素。这样一步一步压下去递归深度会达到n。在Python里递归深度超过一千就会抛出RecursionError就算把递归限制调到十万比较和交换次数也接近123...n也就是O(n²)。十万个有序元素顶配机器也要跑几十秒。逆序数组同理固定取第一个元素时每次选到的是最大值情况一样惨。我开头提到的那个“卡死”就是踩中了这个坑。1.3 随机化的本质把最坏情况的触发条件洗掉固定枢轴的真正问题不是“最坏情况存在”而是“最坏情况可以被输入精确命中”。你甚至不需要恶意构造数据只要数据来源本身有某种顺序比如数据库查询结果按ID升序返回就会稳定触发退化。随机枢轴的思路是每次从当前区间随机选一个位置作为枢轴而不是用固定位置。这样哪怕输入数据是升序、逆序、或带某种规律每一次分区对枢轴位置都没有确定性预判。出现极度不平衡划分的概率被拉得非常低几乎可以认为不会发生。从期望复杂度来看随机枢轴快排仍然是O(n log n)但最坏情况退化变成需要连续手气差到极点才可能触发的事件。以十万个元素为例连续这么多次都选到边缘元素概率比买彩票低得多。所以工程上可以放心使用。2. 实现随机枢轴的两种姿势预洗牌与选中交换2.1 方法一先打乱整个输入一种很容易想到的思路是排序前先用random.shuffle()把整个数组打乱然后继续用固定的“取第一个元素”策略。这样每次排序前输入已经是乱序固定枢轴退化的概率也会被压下去。这个思路在数学上没问题因为均匀洗牌之后任意一个元素落在“区间第一个位置”上的概率相同等价于随机枢轴。但工程上我不推荐原因有三个第一shuffle是O(n)操作虽然不影响总复杂度但多了一整轮遍历。第二它修改了原数组的顺序调用方拿到的排序结果虽然有序但已经丢失了“排序前原本的相对顺序”信息某些场景下会影响后续业务。第三每次都做全数组洗牌和“只洗一个枢轴元素”相比单位成本高了一个数量级数据量越大越明显。2.2 方法二随机索引与边界交换我的默认选择推荐做法是只随机选一个索引然后把它和当前区间左端元素交换之后完全复用固定枢轴的分区逻辑。这样每次只做一次常数时间的swap既不需要O(n)洗牌也不会污染原数组的额外信息。代码长这样import random def partition(nums, left, right): pivot_idx random.randint(left, right) nums[left], nums[pivot_idx] nums[pivot_idx], nums[left] pivot nums[left] i left 1 j right while True: while i j and nums[i] pivot: i 1 while i j and nums[j] pivot: j - 1 if i j: break nums[i], nums[j] nums[j], nums[i] i 1 j - 1 nums[left], nums[j] nums[j], nums[left] return j def quicksort_random(nums, left0, rightNone): if right is None: right len(nums) - 1 if left right: return mid partition(nums, left, right) quicksort_random(nums, left, mid - 1) quicksort_random(nums, mid 1, right)关键点就是第一行先把随机选中的枢轴换到left位置后面所有逻辑都当作固定枢轴处理。这样最省事也最容易验证。2.3 randint的边界细节闭区间别写错经常有人在这翻车random.randint(left, right)返回的是闭区间[left, right]两个端点都能取到。如果写成random.randrange(left, right)那就是左闭右开取不到right。排序区间是包含right的所以必须用randint或者用random.randrange(left, right 1)。另一个细节是当区间只剩一个元素时left等于rightrandint返回的就是这个索引交换成了自己和自己换没有副作用逻辑仍然正确。所以在入口判断left right之后partition内部不需要再额外做“单元素直接返回”的兜底。3. 分区扫描的两种流派单指针和双指针的取舍3.1 单指针扫描写法简单但有一笔隐形成本教科书里常见的是单指针扫描法维护一个“小于枢轴的区域”的边界index从头到尾遍历一次遇到比枢轴小的元素就把它和index位置的元素交换index加一最后再把枢轴换到index位置。这个写法看起来更简洁代码也不容易写错。但它的实际开销不小。最明显的一点是它必须完整遍历整个区间哪怕某个元素早就已经处在正确的一侧仍然会发生一次无意义的交换。对于“大量元素恰好有序”的输入这种不必要的交换会被放大。另外单指针扫描对等于枢轴的元素没有统一处理策略容易让等于枢轴的元素在左右两侧反复交换增加工作量。3.2 双指针相向扫描原地交换的经典方案我上面代码里用的就是双指针相向扫描i从左边走j从右边走。i跳过比枢轴小的元素j跳过比枢轴大的元素停下来后i指向一个不小于枢轴的元素j指向一个不大于枢轴的元素此时如果i还没越过j就交换这两个“不该在当前位置”的元素。双指针的优势是最终只有跨过中线的元素才会交换位于正确区域的元素完全不会被打扰。在数据本身较有序、或者枢轴恰好接近中位数时需要移动的元素很少扫描开销明显低于单指针方案。这也是为什么工程实现普遍倾向这类双指针分区。有个容易混淆的点这个分区方案和快速排序的“稳定性”无关。如果你需要保留相等元素的相对顺序快速排序本身就不是稳定排序随机化不会改变这一点不要为了这个去迁就分区方式。3.3 随机枢轴在分区里最容易踩的边界坑随机枢轴和双指针分区结合时有一个常见的死循环写法内层循环里不判断i j而是让i和j无限制地相向走可能越过中线后继续跑出边界导致数组越界。所以我保留了i j的判断两个内层while都带上这个前提。另一个容易踩的是交换完nums[i]和nums[j]之后如果忘了让i加一、j减一下一次外层循环时这两个位置又会被卡住进入无限循环。很多新手在调试时发现“排序半天出不来”最后定位到的是这里而不是随机数生成的问题。调试这类分区逻辑我建议先用几十个随机小数组做“性质测试”跑完排序后检查结果是否等于排序后的正确序列同时把递归深度和交换次数打出来。小数组能迅速暴露边界问题别一上来就丢到十万数据里去验证。4. 重复元素和递归深度随机枢轴覆盖不到的盲区4.1 为什么重复元素会让分区形同虚设很多人以为随机枢轴能解决一切退化场景其实它解决不了大量重复元素的问题。比如一个数组里90%的元素都等于同一个值随机枢轴大概率也是这个值。这时候双指针扫描的问题就暴露了i会发现很多等于枢轴的元素j也会发现很多等于枢轴的元素于是两指针频繁交换这些相等的元素交换完之后i和j只前进了很小一段。更关键的是分区结束后等于枢轴的那些元素会被分到左右两侧而不是集中在中间递归时它们还会反复参与排序。如果重复元素形成某种连续分布分区很容易产生严重不均衡的空区间退化成O(n²)。4.2 三路分区把相等元素一次性归位处理重复数据的标准解法是三路分区把区间划分为小于枢轴、等于枢轴、大于枢轴三个区域。等于枢轴的元素全部留在中间不进入后续递归。这样不仅跳过无意义的重复比较还保证了重复数据场景下还是O(n log n)。三路分区配合随机枢轴是这样实现的def quicksort_three_way(nums, left, right): if left right: return pivot_idx random.randint(left, right) pivot nums[pivot_idx] lt left # 小于区的下一个待交换位置 gt right # 大于区的前一个待交换位置 i left while i gt: if nums[i] pivot: nums[lt], nums[i] nums[i], nums[lt] lt 1 i 1 elif nums[i] pivot: nums[i], nums[gt] nums[gt], nums[i] gt - 1 else: i 1 quicksort_three_way(nums, left, lt - 1) quicksort_three_way(nums, gt 1, right)三个区域在同一个循环里同步维护lt指向小于区的边界gt指向大于区的边界i负责遍历。当nums[i]大于pivot时把它换到gt位置gt减一但此时i不动因为换过来的新元素还没比较过。这个细节是最容易写错的少写了“i不动”的逻辑就会漏比较元素。实测下来三路分区在处理“大量重复”的数据时往往比双指针方案快一倍以上而在乱序数据上也不会明显变慢是非常值得掌握的一种写法。4.3 sys.setrecursionlimit解决不了根本问题随机枢轴下的期望递归深度是O(log n)十万个元素平均深度也就二三十远够不到Python默认的一千限制。但如果你用的是固定枢轴或者三路分区写错导致递归深度失控去调sys.setrecursionlimit只是在表面止损深层依然是算法退化。我见过有人在排序代码里设置一个很大的递归深度然后继续跑出O(n²)时间还以为是Python递归性能差。其实换个思路想想一旦递归深度达到数万说明每次分区都在做无用功这时候应该改进分区逻辑而不是提高递归上限。如果数据集真的又大又偏后续我会在第六节讲怎么用显式栈避免递归深度问题。5. 实测表现四类典型数据下随机枢轴的成绩单5.1 测试方案与数据构造我在一台普通配置的笔记本上做了基准测试数据规模统一为十万个整数构造四类输入完全随机的乱序数组、已经升序排列的数组、已经逆序排列的数组、包含约80%重复元素的重度重复数组。测试对象有三个固定取第一个元素作枢轴的双指针快排、随机枢轴双指针快排、随机枢轴三路分区快排。每类数据跑五次取最短时间避免机器波动影响结论。固定枢轴版本在升序和逆序数据上因为递归深度会超过限制我先调大了递归上限让它能真正跑完这样得到的时间才是算法退化后的真实代价。5.2 结果对比与解读测试数据只是我这台机器上的结果主要看相对趋势输入类型固定枢轴双指针随机枢轴双指针随机枢轴三路分区完全乱序0.24s0.25s0.27s升序约30.6s0.21s0.19s逆序约28.4s0.22s0.20s重度重复0.34s0.30s0.13s三个对象在完全乱序数据上基本持平随机枢轴比固定枢轴慢一点点这部分差距就是random.randint本身的成本大约几个百分点。升序和逆序数据就能看出来差距有多大固定枢轴的时间是随机枢轴的一百倍以上。重度重复数据上随机枢轴双指针有一点优势但真正的改观来自三路分区耗时几乎只有双指针版本的一半。5.3 从实测看随机化带来的收益和代价随机枢轴在“数据本身有规律”的场景里收益是数量级的在“数据完全乱序”的场景里代价是几个百分点的额外耗时。这个取舍几乎不需要犹豫真实业务数据很少是理想乱序的反而经常带有排序特征比如主键ID递增、日志时间戳递增、历史报表值存在大量重复。三路分区在重复数据上优势明显所以我现在的默认方案是随机枢轴加三路分区。在普通数据上它不比双指针慢在重复数据上还能收获额外性能。如果你手头的业务场景对重复值和有序数据容忍度都很低这套组合是最稳的选择。6. 从玩具代码到能用的排序细节决定成败6.1 随机数生成random模块是否足够可靠random模块用的是梅森旋转伪随机算法对于一个不涉及安全对抗的排序场景完全够用。排序任务对随机性最真实的诉求是“不可预测的均匀分布”而不是加密级随机所以不需要引入secrets模块。代码里每次调用random.randint会触发一次随机数获取对性能有一点影响但和排序本身的比较与交换开销相比可以忽略。有一点值得提如果你在写单元测试希望通过固定随机种子复现排序过程可以在测试函数开头写random.seed(42)。这不会影响生产代码但能帮你稳定复现某个边界情况。我习惯在调试和性能验证时固定种子确认无误后再去掉避免在调试过程中被随机性干扰。6.2 递归改显式栈的时机虽然随机枢轴把递归深度控制在O(log n)但有些场景我还是会改成显式栈一是要彻底避开递归限制二是有可能把排序任务拆给多线程并行处理用栈存储待排序区间会比递归调用更容易控制任务粒度。显式栈版本只需要一个列表当作栈存放(left, right)区间二元组循环弹出处理分区后再把左右两个子区间压回栈。压栈顺序不影响正确性但如果你介意缓存局部性可以优先压较大的区间、先处理较小的区间这样栈空间更小。伪代码如下def quicksort_iterative(nums): stack [(0, len(nums) - 1)] while stack: left, right stack.pop() if left right: continue mid partition(nums, left, right) if mid - 1 left: stack.append((left, mid - 1)) if mid 1 right: stack.append((mid 1, right))老实说纯Python手写快排的性能始终无法和内置排序竞争改迭代不是为了快而是为了可控。我在少量特殊任务里会用这种结构把排序区间切成几大块分发给不同进程处理这时候显式栈的价值就显现了。6.3 和Python内置排序的关系以及我的最终建议Python内置的排序算法虽然我不擅长叫它正式的算法名但它是混合了多种策略的高性能实现内部处理了小数组时改用插入排序、检测输入是否几乎有序、以及对待排序元素做适当缓存等优化。绝大多数业务场景直接调用sort()或sorted()就是最优解不需要也不应该自己写排序。那么手写随机枢轴快排的价值在哪里第一是在学习层面它能让你真正理解分治、枢轴、分区、退化这些概念到底怎么运作第二是在某些受控环境里比如教学项目、数据结构课程、或对排序行为有特殊定制的脚本你可能需要自己控制排序过程第三是面试时总是绕不开这道题。我的个人建议是会写、能讲清楚、知道什么时候不该用比把它强行塞进生产代码更重要。再补一个不算冷门的小技巧如果你确实想在Python里复刻fast sort的底层思路但又不想完全手写可以在C扩展层面参考随机枢轴加三路分区但这已经是另一篇文章的话题了。目前这份代码和思路已经足够支撑绝大多数学习和二次开发的需要。