随机快速排序这个东西我最早是在刷算法课的时候被它坑过的。当时觉得快排嘛不就是选个基准、分个左右、递归下去写出来跑通就完事了。结果一上测试用例有序数组直接退化成平方复杂度递归深度爆栈当场傻眼。后来才明白快排真正的分水岭不在于“会不会写”而在于“敢不敢随机”。左程云算法通关系列里专门把随机快排拎出来讲本质上就是在解决这个最容易被忽视、却最致命的工程问题当输入数据不配合你的假设时算法还能不能稳住。这篇内容我想从一个写过无数遍快排、也踩过无数遍坑的从业者角度把随机快速排序这件事彻底拆开。它是什么一句话就是在经典快排的基础上用随机方式选取基准元素把“最坏情况”从必然事件变成概率事件。它能做什么让排序在绝大多数真实场景下稳定跑在 O(N log N) 附近而不是被一组精心构造的数据打回 O(N²)。适合谁看如果你已经能默写基础快排但对“为什么要随机”“随机之后复杂度怎么算”“三路划分到底解决什么问题”还模棱两可那这篇就是写给你的。下面我会从设计思路、核心细节、完整实操到踩坑排查一层层往下剥。1. 随机快排到底在解决什么问题1.1 经典快排的“阿喀琉斯之踵”经典快排的逻辑很朴素拿一个基准值把数组分成“小于等于基准”和“大于基准”两堆然后对两堆分别递归。理想情况下每次划分都接近对半递归树高度是 log N每层总工作量是 N乘起来就是 O(N log N)。这个推导没问题问题出在“理想情况”这四个字上。基准值怎么选最偷懒的做法是固定选第一个元素或者最后一个元素。这个选择在随机数据上看起来没事因为数据本身乱基准值落在中间的概率不小。但真实世界的数据往往不是随机的。我见过太多场景数据库导出的主键基本有序、日志按时间戳追加、用户 ID 递增写入。这些数据送到固定选首元素的快排面前每一次划分都会把数组切成“1 个元素 剩下全部”递归树直接退化成一条链高度变成 N总工作量变成 N (N-1) ... 1也就是 O(N²)。更难受的是递归深度。链状递归意味着调用栈深度达到 N数据量一大就直接栈溢出。这不是理论上的担忧是实打实会崩的。所以经典快排的软肋不是“平均性能差”而是“对输入分布过于敏感”一旦输入有规律性能就雪崩。1.2 随机化把确定性最坏变成概率最坏随机快排的核心动作只有一个不再固定选某个位置的元素当基准而是在当前区间里等概率随机挑一个位置把它和区间首元素交换然后拿首元素当基准。就这么一个交换性质完全变了。为什么因为最坏情况仍然存在——只要你每次随机都恰好挑到当前区间的最大值或最小值还是会退化。但这件事发生的概率是多少对于长度 N 的数组第一次挑中极值的概率是 2/N第二次是 2/(N-1)一路乘下去这个概率小到可以忽略。换句话说随机化没有消灭最坏情况而是把它从“只要输入有序就必然发生”变成了“需要一连串巧合才发生”。这里有个很多人没想透的点随机快排的复杂度分析是对“随机选择”这个随机变量求期望而不是对输入数据求平均。也就是说不管你给我什么数据——有序的、逆序的、全相等的、精心构造的——我的期望复杂度都是 O(N log N)。这个性质叫“去随机化依赖”是随机算法最值钱的地方。你不需要假设用户数据是随机的算法自己制造随机性来保护自己。1.3 期望复杂度 O(N log N) 的直觉推导严格证明要用指示器随机变量但我想给一个更直观的版本方便你建立感觉。考虑数组中任意一对元素 (i, j)它们在排序过程中会不会被比较只有当这两个元素曾经落在同一个子区间、并且其中一个被选为基准时它们才会比较一次。一旦某个元素被选为基准它就和区间内所有其他元素比较然后被放到最终位置之后再也不参与。关键在于对于第 k 小的元素和第 m 小的元素假设 k m它们被比较的概率等于“在它们之间含两端的所有元素中第一个被选为基准的恰好是这两个之一”。因为如果先选中的是中间某个元素这两个就会被分到不同子区间永远不会比较。在 m - k 1 个候选里两端被先选中的概率是 2/(m - k 1)。把所有元素对的比较概率加起来总比较次数的期望就是 Σ 2/(m-k1)这个求和可以整理成 O(N log N)。这个推导的美妙之处在于它完全不关心输入长什么样只依赖“随机选基准”这一个事实。所以你可以放心地对任何数据用随机快排期望性能都有保证。2. 核心细节划分方案与随机化的实现要点2.1 两种划分方式的选择双指针 vs 三路快排的划分方案有好几种最常被拿来对比的是双指针划分和三路划分。双指针划分把数组分成“小于等于基准”和“大于基准”两段适合元素基本不重复的场景。三路划分把数组分成“小于基准”“等于基准”“大于基准”三段专门对付大量重复元素。为什么这个区别重要考虑一个极端例子数组里一万个元素全是同一个值。双指针划分每次只能把基准值本身归位剩下的元素全跑到一边递归下去还是同样的局面复杂度退化成 O(N²)。而三路划分一次就能把所有等于基准的元素全部归位重复元素再多也是一次搞定复杂度稳定在 O(N log N)。我的建议很直接默认用三路划分。它在无重复数据上的开销比双指针略大一点点多维护两个指针但换来的是对重复数据的完全免疫。真实业务里重复值太常见了——状态字段、分类标签、评分数据哪个不是大量重复为了省那一点点常数因子去赌数据不重复不划算。2.2 随机交换的位置与时机随机化的实现有个细节容易被写错随机选中的位置要和谁交换标准做法是和当前区间的左边界交换然后以左边界元素作为基准。这个顺序不能乱。我见过有人写成“先取左边界当基准再随机交换别的位置”这就等于没随机因为基准已经定死了。正确顺序是先在 [left, right] 范围内生成随机下标把这个下标的元素和 left 位置的元素交换此时 left 位置放的就是随机选中的值再拿它当基准。这样基准的分布才是均匀的。随机数生成也有讲究。用语言自带的伪随机函数就行但要注意种子。如果每次运行都用固定种子虽然单次运行内部是随机的但多次运行结果可复现——这在调试时是好事在生产环境如果被恶意构造输入针对理论上存在被预测的风险。不过对绝大多数业务场景默认种子足够用不必过度设计。2.3 三路划分的指针维护逻辑三路划分是随机快排里最容易写错的部分我用文字把过程走一遍。维护三个指针lt指向“小于区”的右边界初始为 lefti是当前扫描位置初始为 left1gt指向“大于区”的左边界初始为 right1。基准值取arr[left]。扫描规则分三种情况。当arr[i]小于基准把它和arr[lt1]交换lt和i同时右移。当arr[i]大于基准把它和arr[gt-1]交换gt左移注意此时i不动因为换过来的元素还没检查。当arr[i]等于基准i直接右移。循环结束条件是i gt。最后把基准值arr[left]和arr[lt]交换此时lt位置就是基准的最终位置[left, lt-1]是小于区[lt, gt-1]是等于区[gt, right]是大于区。递归只需要处理小于区和大于区等于区已经全部归位。注意大于区交换后i不前进这一点是初学者最高频的 bug 来源。换过来的元素来自未扫描区域必须重新判断否则会漏检甚至死循环。2.4 递归边界与小区间优化递归的终止条件是left right这个没什么好说的。但有个工程优化值得提当区间长度小于某个阈值常见取 16 到 32时改用插入排序。原因是小区间上递归调用的开销压栈、随机数生成、函数调用占比太高而插入排序在近乎有序的小数组上常数极小。这个优化不是必须的但实测下来对整体性能有可见提升尤其是数据量在几万到几十万这个区间。阈值取多少我一般取 16太小了优化不明显太大了插入排序的平方开销开始显现。你可以自己压测调但 16 是个稳妥的默认值。3. 完整实操从零实现一个随机三路快排3.1 整体代码骨架我用 Python 写一版逻辑清晰优先性能敏感的场景可以换 C 或 Java思路完全一致。先看骨架import random def random_quick_sort(arr): if len(arr) 2: return arr _quick_sort(arr, 0, len(arr) - 1) return arr def _quick_sort(arr, left, right): if left right: return # 小区间优化 if right - left 1 16: _insertion_sort(arr, left, right) return # 随机选基准并交换到左边界 rand_idx random.randint(left, right) arr[left], arr[rand_idx] arr[rand_idx], arr[left] # 三路划分 lt, gt _partition_three_way(arr, left, right) # 递归两侧 _quick_sort(arr, left, lt - 1) _quick_sort(arr, gt, right)这个骨架里_partition_three_way返回等于区的左右边界递归时跳过整个等于区。注意递归调用传的是lt - 1和gt不是lt和gt因为lt到gt-1是等于区已经归位。3.2 三路划分函数的逐行实现def _partition_three_way(arr, left, right): pivot arr[left] lt left # 小于区右边界 i left 1 # 当前扫描指针 gt right 1 # 大于区左边界 while i gt: if arr[i] pivot: arr[lt 1], arr[i] arr[i], arr[lt 1] lt 1 i 1 elif arr[i] pivot: arr[gt - 1], arr[i] arr[i], arr[gt - 1] gt - 1 # i 不前进 else: i 1 # 基准归位 arr[left], arr[lt] arr[lt], arr[left] return lt, gt这段代码我建议你手写三遍尤其是arr[i] pivot分支里i不前进这个点。很多人第一次写会条件反射地i 1然后发现结果错乱。原因前面说过换过来的元素来自gt-1是未扫描区域的值必须重新判断。3.3 插入排序辅助函数def _insertion_sort(arr, left, right): for i in range(left 1, right 1): key arr[i] j i - 1 while j left and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key插入排序在小区间上的优势在于没有递归开销内层循环对近乎有序的数据几乎不移动元素。配合随机快排的“大区间随机划分、小区间插入排序”策略整体性能会比纯递归版本好一截。3.4 参数选择与压测记录我拿几组数据做过对比环境是普通笔记本Python 3.10数据量 100 万随机整数。纯双指针快排固定基准在有序数据上直接超时随机三路快排稳定在 1.2 秒左右加小区间优化后降到 1.0 秒上下。阈值从 8 调到 32 都试过16 和 24 差别不大16 略稳。这里给个经验值参考表数据特征推荐方案理由大量重复元素三路划分等于区一次归位避免退化基本有序随机基准 三路随机化打散有序性数据量小于 50直接插入排序递归开销不划算数据量 50 到 10 万随机三路 小区间优化综合性能最优内存敏感场景原地划分不用额外数组空间 O(log N) 仅递归栈提示如果你在面试里被要求手写快排先问一句“数据有没有大量重复”然后主动上三路划分这个细节能明显加分。4. 常见问题与排查实录4.1 递归爆栈怎么破随机快排的期望递归深度是 O(log N)但最坏情况理论上还是 O(N)。虽然概率极低但工程上不能完全不管。两个应对手段一是小区间优化把深度较深的小区间截断成插入排序实际递归深度会显著降低二是手动模拟栈或者尾递归优化先递归较短的一侧较长的一侧用循环处理这样栈深度上界压到 O(log N)。我一般用第二种改动很小划分完之后比较左右两段长度短的先递归长的用 while 循环继续处理。这个技巧在数据量上千万时能救命。4.2 结果不对的排查顺序快排写错症状通常是“部分有序但整体乱”或者“死循环”。排查我按这个顺序走先检查划分函数的指针移动尤其是大于区交换后i是否误前进再检查基准归位那一步arr[left]和arr[lt]交换后返回的边界对不对最后检查递归区间是不是把等于区又递归进去了。九成的 bug 出在前两步。4.3 随机化没生效的隐蔽写法有一种错误很隐蔽随机下标生成了也交换了但基准值是在交换之前就取好的。比如先pivot arr[left]再随机交换这样基准还是原来的值随机化形同虚设。正确顺序永远是“先随机交换再取基准”。这个坑我在 review 别人代码时见过不止一次肉眼很难一眼看出来因为代码看起来“有随机”。4.4 常见问题速查表现象可能原因解决方向有序数据超时基准固定未随机化加随机交换步骤全相等数据超时双指针划分退化改三路划分结果局部乱序大于区交换后 i 误前进该分支不移动 i死循环递归区间包含等于区递归用 lt-1 和 gt栈溢出递归深度过大短边先递归长边循环随机后仍退化基准在交换前取值调整取值顺序4.5 一个容易被忽略的稳定性问题快排是不稳定排序这一点很多人知道但不当回事。如果你的业务要求相同键值的元素保持原始相对顺序——比如先按时间排好、再按状态排希望同状态内保持时间序——那快排会打乱它。这种场景要么换归并排序要么在比较键里加上原始下标做二次比较。我踩过这个坑排序完发现同组数据顺序变了排查半天才想起来是不稳定排序的锅。5. 随机快排的边界与替代方案5.1 什么时候不该用快排快排虽好但不是万能。数据量很小几十个元素时插入排序更直接要求稳定排序时归并是更稳的选择数据分布在外部存储、需要顺序访问时归并的外部版本更合适对最坏情况有硬性时间保证的场景比如实时系统堆排序的确定性更让人放心。随机快排的定位是“通用内存排序的默认优选”不是“所有场景的唯一答案”。5.2 与内省排序的关系工业级排序库比如很多标准库的 sort 实现用的往往不是纯快排而是内省排序快排为主递归深度超过阈值时切换堆排序保证最坏 O(N log N)小区间切插入排序。随机快排可以看作内省排序的简化版少了深度监控那一层。如果你要写生产级排序建议直接参考内省排序的思路把随机化和深度保护都加上。5.3 随机化思想的迁移随机选基准这个思路本质是“用随机性对抗输入的不确定性”这个思想可以迁移到很多地方。比如哈希表的冲突处理、负载均衡的节点选择、采样估算的偏差消除背后都是同一个逻辑当对手可能构造最坏输入时主动引入随机性把确定性劣势变成概率优势。理解随机快排不只是学会一个排序算法更是建立一种工程防御的思维习惯。我个人在实际操作中的体会是随机快排最值得反复琢磨的不是代码本身而是“为什么一个交换就能改变复杂度性质”这个推理链条。把这个链条想通了你再去看其他随机算法会有一种似曾相识的通透感。另外提醒一句手写三路划分时别偷懒用额外数组原地划分虽然指针绕但空间复杂度从 O(N) 降到 O(log N)数据量大的时候差别很明显。最后分享一个小技巧调试划分逻辑时拿一个只有五六个元素、包含重复值的小数组手动模拟每一步指针位置比盯着代码看有效得多。