随机快速排序这个东西，我最早是在刷算法课的时候被它坑过的。当时觉得快排嘛，不就是选个基准、分个左右、递归下去，写出来跑通就完事了。结果一上测试用例，有序数组直接退化成平方复杂度，递归深度爆栈，当场傻眼。后来才明白，快排真正的分水岭不在于“会不会写”，而在于“敢不敢随机”。左程云算法通关系列里专门把随机快排拎出来讲，本质上就是在解决这个最容易被忽视、却最致命的工程问题：当输入数据不配合你的假设时，算法还能不能稳住。

这篇内容我想从一个写过无数遍快排、也踩过无数遍坑的从业者角度，把随机快速排序这件事彻底拆开。它是什么？一句话，就是在经典快排的基础上，用随机方式选取基准元素，把“最坏情况”从必然事件变成概率事件。它能做什么？让排序在绝大多数真实场景下稳定跑在 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-k+1)，这个求和可以整理成 O(N log N)。这个推导的美妙之处在于，它完全不关心输入长什么样，只依赖“随机选基准”这一个事实。所以你可以放心地对任何数据用随机快排，期望性能都有保证。

2. 核心细节：划分方案与随机化的实现要点

2.1 两种划分方式的选择：双指针 vs 三路

快排的划分方案有好几种，最常被拿来对比的是双指针划分和三路划分。双指针划分把数组分成“小于等于基准”和“大于基准”两段，适合元素基本不重复的场景。三路划分把数组分成“小于基准”“等于基准”“大于基准”三段，专门对付大量重复元素。

为什么这个区别重要？考虑一个极端例子：数组里一万个元素全是同一个值。双指针划分每次只能把基准值本身归位，剩下的元素全跑到一边，递归下去还是同样的局面，复杂度退化成 O(N²)。而三路划分一次就能把所有等于基准的元素全部归位，重复元素再多也是一次搞定，复杂度稳定在 O(N log N)。

我的建议很直接：默认用三路划分。它在无重复数据上的开销比双指针略大一点点（多维护两个指针），但换来的是对重复数据的完全免疫。真实业务里重复值太常见了——状态字段、分类标签、评分数据，哪个不是大量重复？为了省那一点点常数因子去赌数据不重复，不划算。

2.2 随机交换的位置与时机

随机化的实现有个细节容易被写错：随机选中的位置，要和谁交换？标准做法是和当前区间的左边界交换，然后以左边界元素作为基准。这个顺序不能乱。

我见过有人写成“先取左边界当基准，再随机交换别的位置”，这就等于没随机，因为基准已经定死了。正确顺序是：先在 [left, right] 范围内生成随机下标，把这个下标的元素和 left 位置的元素交换，此时 left 位置放的就是随机选中的值，再拿它当基准。这样基准的分布才是均匀的。

随机数生成也有讲究。用语言自带的伪随机函数就行，但要注意种子。如果每次运行都用固定种子，虽然单次运行内部是随机的，但多次运行结果可复现——这在调试时是好事，在生产环境如果被恶意构造输入针对，理论上存在被预测的风险。不过对绝大多数业务场景，默认种子足够用，不必过度设计。

2.3 三路划分的指针维护逻辑

三路划分是随机快排里最容易写错的部分，我用文字把过程走一遍。维护三个指针：lt指向“小于区”的右边界（初始为 left），i是当前扫描位置（初始为 left+1），gt指向“大于区”的左边界（初始为 right+1）。基准值取arr[left]。

扫描规则分三种情况。当arr[i]小于基准，把它和arr[lt+1]交换，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 略稳。

这里给个经验值参考表：

提示：如果你在面试里被要求手写快排，先问一句“数据有没有大量重复”，然后主动上三路划分，这个细节能明显加分。

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 常见问题速查表

4.5 一个容易被忽略的稳定性问题

快排是不稳定排序，这一点很多人知道但不当回事。如果你的业务要求相同键值的元素保持原始相对顺序——比如先按时间排好、再按状态排，希望同状态内保持时间序——那快排会打乱它。这种场景要么换归并排序，要么在比较键里加上原始下标做二次比较。我踩过这个坑，排序完发现同组数据顺序变了，排查半天才想起来是不稳定排序的锅。

5. 随机快排的边界与替代方案

5.1 什么时候不该用快排

快排虽好，但不是万能。数据量很小（几十个元素）时，插入排序更直接；要求稳定排序时，归并是更稳的选择；数据分布在外部存储、需要顺序访问时，归并的外部版本更合适；对最坏情况有硬性时间保证的场景（比如实时系统），堆排序的确定性更让人放心。随机快排的定位是“通用内存排序的默认优选”，不是“所有场景的唯一答案”。

5.2 与内省排序的关系

工业级排序库（比如很多标准库的 sort 实现）用的往往不是纯快排，而是内省排序：快排为主，递归深度超过阈值时切换堆排序保证最坏 O(N log N)，小区间切插入排序。随机快排可以看作内省排序的简化版，少了深度监控那一层。如果你要写生产级排序，建议直接参考内省排序的思路，把随机化和深度保护都加上。

5.3 随机化思想的迁移

随机选基准这个思路，本质是“用随机性对抗输入的不确定性”，这个思想可以迁移到很多地方。比如哈希表的冲突处理、负载均衡的节点选择、采样估算的偏差消除，背后都是同一个逻辑：当对手可能构造最坏输入时，主动引入随机性把确定性劣势变成概率优势。理解随机快排，不只是学会一个排序算法，更是建立一种工程防御的思维习惯。

我个人在实际操作中的体会是，随机快排最值得反复琢磨的不是代码本身，而是“为什么一个交换就能改变复杂度性质”这个推理链条。把这个链条想通了，你再去看其他随机算法，会有一种似曾相识的通透感。另外提醒一句，手写三路划分时别偷懒用额外数组，原地划分虽然指针绕，但空间复杂度从 O(N) 降到 O(log N)，数据量大的时候差别很明显。最后分享一个小技巧：调试划分逻辑时，拿一个只有五六个元素、包含重复值的小数组，手动模拟每一步指针位置，比盯着代码看有效得多。