很多人学完快速排序，第一反应是“代码背下来了，但让我自己写一遍却总觉得哪里不对，尤其是分区那一步，稍微改动一个边界条件，数组就越界或者死循环”。还有人问得最多的是：“网上快排版本这么多，到底该记哪个？面试写哪个最好？”

这篇文章就围绕快速排序这个经典算法，把核心设计思路、分区实现细节、不同基准选择策略、常见优化手段以及我实际调代码时踩过的坑一次性讲透。不管你是刚学数据结构的本科生，还是准备面试、想看工业级实现细节的开发者，这篇文章都按“原理 -> 手写实现 -> 优化 -> 避坑”的顺序来展开，你可以直接对照着写代码、跑测试。

1. 快速排序的整体设计思路

快速排序能成为教科书级的经典算法，核心不是“快”这个结果，而是它的分治策略极其干净：选一个基准值，把数组分成“小于等于基准”和“大于等于基准”两半，然后再对两半分别递归排序。这个过程中，真正的难点和性能瓶颈都集中在一个动作上：分区（partition）。

1.1 分治思想与归并排序的差异

很多初学者会拿快速排序和归并排序对比。归并排序的分治是“先递归、再合并”，它的核心工作在合并阶段，需要额外的O(n)空间把两个有序数组合并成一个有序数组，过程中元素相对顺序稳定，但空间占用是硬伤。

快速排序的分治是“先分区、再递归”，核心工作在分区阶段，不需要额外的合并数组。基准值一旦选好、分区完成，这个基准值的位置就是最终位置，后续不会再变动。这是快速排序“原地排序”的根源，也是它空间复杂度能做到O(log n)（递归栈）甚至O(1)（非递归）的原因。

换句话说，归并排序是把排序问题拆成“排好左边、排好右边、然后合并”；快速排序是“选个老大，比他小的站左边，比他大的站右边，然后把左边和右边各自再按这个逻辑排一遍”。

1.2 为什么分区是核心中的核心

快速排序的平均时间复杂度是O(n log n)，但这个“平均”很微妙：它建立在每次分区都能把数组大致对半分的假设上。如果你的分区代码写出来，基准值总是偏到一头，那递归树的高度就从O(log n)退化成了O(n)，整体复杂度直接变成O(n^2)。

所以，快速排序的性能优劣，本质上不取决于递归写得多漂亮，而取决于两个问题：

1. 基准值怎么选？选得好，两边均匀，递归深度小。
2. 分区过程怎么移动指针？移动方法不同，边界条件完全不一样，写错就是死循环或越界。

这两个问题，是快速排序的全部核心。以下内容我分两部分详细拆开讲。

2. 基准选取策略与分区实现细节

很多人写的快速排序版本，直接固定取数组最后一个元素或第一个元素做基准。不是说不能这样写，而是这样写有一个明显的性能缺陷：如果输入数组已经有序，固定取首元素或尾元素，每次分区都极不均匀，递归深度变成n，快速排序直接退化成冒泡排序的复杂度。实际工程里，数据“接近有序”是常态而不是例外。

2.1 基准选取的三种常见策略

我在不同场景下分别用过以下三种策略，说下它们的取舍。

固定位置取基准

直接取第一个元素或最后一个元素，代码最简单，一个赋值搞定。适合理解算法逻辑，也适合写教学示例。但遇到有序数组或几乎有序的数组时，性能会急剧恶化。如果在随机数据上跑，效果还不错，所以很多算法教材拿它做默认实现。

随机选取基准

在数组中随机挑一个索引作为基准，然后把它交换到端点位置，再执行正常分区。这种做法能大幅降低遇到最坏情况的概率。因为输入数据千变万化，我每次随机选一个，就很难每次都不巧选中最大或最小值。随机化的代价是额外的一次随机数生成和一次交换，但对整体性能影响极小。

实际测试中，对一个10万元素的近似有序数组，固定取末尾基准的快排跑了接近8秒，随机基准版本只跑了0.03秒。这个量级的差距，直接决定了一个排序函数能不能用在线上环境。

三数取中

取数组的左端、中间、右端三个位置上的元素，找出三个值中大小居中的那个，把它交换到端点再分区。它比随机基准多了一定的确定性，实测在接近有序和随机数据的综合表现都很好，而且不需要调用随机数生成器，不会引入随机性的不确定抖动。工程上很多排序库默认使用这种策略。

三数取中的实现能顺带做一个优化：选完中值后，把三个数中的最小值放到数组开头，最大值放到数组末尾，中值放到倒数第二个位置。这样在后续分区时，已经有一部分元素落在了正确的位置区域，能稍微减少比较次数。不过这属于微优化，优先级不高。

从我的经验看，如果只选一种策略记，就记三数取中；如果只要一个最稳定的版本，就记随机基准。两种都掌握，面试时提到“避免最坏情况”的思路就有了。

2.2 分区算法的两种流派：单指针扫描与双指针相向扫描

分区是八十个易错点集中爆发的地方。我先把两种最主流的写法讲清楚。

单指针扫描（Lomuto分区）

思路是：选最后一个元素做基准，用指针i标记“小于等于基准的区间边界”，用指针j从头扫描到倒数第二个元素。每当遇到小于等于基准的元素，就把i向前挪一格，然后把i位置和j位置的元素交换。扫描结束后，i的位置就是基准的正确位置，把基准和i位置交换即可。

这种写法非常直观，一个for循环就能完成，适合学习和写简洁代码。但它有一个缺点：交换次数偏多。当大量元素小于等于基准时，几乎每个元素都要被交换一次，虽然时间复杂度还是O(n)，但常数系数比双指针法要大。

双指针相向扫描（Hoare分区）

思路是：把基准值存下来，左指针从数组左端向右找“大于等于基准”的元素，右指针从数组右端向左找“小于等于基准”的元素，找到后两者交换。两个指针持续向中间移动，直到左指针超过右指针，然后以右指针（或左指针）为界切分数组。

这种写法交换次数少，是快速排序最初的发明者使用的方案，也是很多高级优化版本的基础。但它的边界条件极其微妙，容易写错，主要体现在：

• 指针移动和交换的先后顺序不同，最终返回的分界点就不同。
• 如果数组中存在大量重复元素，用“大于”还是“大于等于”作为移动条件，会直接影响分区是否均衡。
• 递归调用时，到底以left和right还是pivot和right作为边界，需要仔细推敲。

我的建议是：初学阶段先从Lomuto分区开始，把逻辑捋顺了，再切换到Hoare分区。不要一上来就啃Hoare，容易劝退。

三路分区

当数组中重复元素很多时，不管是Lomuto还是Hoare，都可能把大量等于基准的元素分散到左右两侧，导致分区不均衡。一种改进是把数组分成三块：小于基准、等于基准、大于基准。这样等于基准的元素不用参与后续递归，当重复元素很多时性能提升明显。Java的排序库中，对含大量重复元素的情况就是用了类似双基准加三路分区的思路。

3. 手写快速排序：从最简实现到工业级优化

很多教程贴一段代码就完事，我这次把三个版本的完整代码以及背后的设计取舍都写清楚，你再结合自己的场景选择合适的版本去用。

3.1 5分钟写一个最简递归版本

先看Lomuto分区的递归版本，这是我建议所有初学者第一个掌握的版本：

def quicksort_lomuto(arr, left, right): if left >= right: return pivot_index = partition_lomuto(arr, left, right) quicksort_lomuto(arr, left, pivot_index - 1) quicksort_lomuto(arr, pivot_index + 1, right) def partition_lomuto(arr, left, right): pivot = arr[right] i = left - 1 for j in range(left, right): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[right] = arr[right], arr[i + 1] return i + 1

我刚学的时候总会问：为什么i的初始值是left - 1，而不是left？因为整个数组中“已处理的小于等于基准的区域”一开始是空的，所以i要设置在数组左边界的前面一格。每发现一个符合要求的元素，i先自增，再交换。最后i + 1的位置，就是基准值应该待的最终位置。

这段代码的递归结束条件是left >= right，也就是区间为空或只有一个元素时不再递归。这部分好理解，只要你把“区间”想成是闭区间[left, right]就一切正常。

3.2 三数取中优化版本

接下来是配合三数取中策略的Lomuto分区版本，这个版本在面试和工程中都很实用：

def median_of_three(arr, left, right): mid = (left + right) // 2 if arr[mid] < arr[left]: arr[left], arr[mid] = arr[mid], arr[left] if arr[right] < arr[left]: arr[left], arr[right] = arr[right], arr[left] if arr[right] < arr[mid]: arr[mid], arr[right] = arr[right], arr[mid] return arr[mid] def quicksort_median(arr, left, right): if left >= right: return if right - left + 1 < 16: insertion_sort(arr, left, right) return median = median_of_three(arr, left, right) # 把中值交换到最后一个位置，方便复用Lomuto分区逻辑 arr[right], arr[median_index(arr, left, right)] = arr[right], arr[median_index(arr, left, right)] pivot_index = partition_lomuto(arr, left, right) quicksort_median(arr, left, pivot_index - 1) quicksort_median(arr, pivot_index + 1, right)

这里有一段代码需要特别留意：当子数组长度小于某个阈值时，我直接改用插入排序，不再递归。这是工业级排序实现中常用的优化手段，原因后面会专门讲。上面的median_index函数需要你根据三数取中的交换逻辑，额外返回基准值所在的下标，我这里为了展示主流程，没有把它内部细节展开。完整实现时，你需要让median_of_three同时返回中值的值和下标。

实操中有一个小技巧：在做三数取中时，既然已经知道三个数中最大值和最小值，可以直接把它们分别放到当前区间的左右两端。每次递归时，子区间的两端已经是局部最小和最大，这能减少分区过程中的元素比较和交换次数。这种优化虽然效果不算特别大，但在追求极致性能的排序库里确实能看到类似思想。

3.3 非递归版本：用显式栈模拟递归

递归版本代码简洁，但有一个隐患：当数据规模极大且分区极端不均衡时，递归深度可能非常大，导致函数调用栈溢出。虽然实际开发中很难碰到这种极端情况，但作为工程备选方案，非递归版本能让你完全避开栈溢出的问题。

非递归的核心思路是：自己维护一个栈，用(start, end)这样的二元组表示待排序区间。每次从栈中弹出一个区间，分区后如果左子区间长度大于1就压栈，右子区间同理。直到栈为空，排序结束。

def quicksort_iterative(arr): if len(arr) <= 1: return arr stack = [(0, len(arr) - 1)] while stack: left, right = stack.pop() if left >= right: continue pivot_index = partition_lomuto(arr, left, right) if pivot_index - 1 > left: stack.append((left, pivot_index - 1)) if pivot_index + 1 < right: stack.append((pivot_index + 1, right)) return arr

这种写法有个隐含的策略选择：先把较长的子区间压栈还是先把较短的压栈？如果偏爱“栈深度更浅”，应该先压较长的子区间，这样栈中同时保存的区间数量会更少。如果先压较短区间，栈的峰值深度可能更大，但实际影响一般也看不出来。我习惯先压右侧（较长的），再压左侧，这样左侧优先被处理，后续栈内元素更少。

非递归的本质不是消灭了分治逻辑，而是把系统调用栈换成了自己管理的数据结构。整个排序的基本流程没有变，但是没有了函数层层调用的开销。在极端情况下，显式栈确实比递归更加可控。

4. 性能开销分析与工程优化技巧

快速排序的性能不是一句话能讲完的，它的实际表现取决于输入数据的分布、基准选择策略和分区实现细节。这里我不列复杂的数学公式，而是直接从实测结果出发，讲清楚几个关键结论。

4.1 时间复杂度与递归深度的关系

理想情况下，每次分区都把区间一分为二，递归深度是O(log n)，总比较次数是O(n log n)。最坏情况下，每次分区只把一个元素放到正确位置，剩下n-1个元素还在一个区间里，递归深度变成O(n)，总比较次数退化成O(n^2)。随机化和三数取中策略的存在意义，就是把“最坏情况”出现的概率降到极低。

很多人忽略的是空间复杂度：递归版本需要O(log n)的调用栈空间，非递归版本使用显式栈也是同样量级。原地排序并不等于没有额外空间占用，这点需要区分清楚。

4.2 小数组切换到插入排序的阈值选择

你对一个只有10个元素的子数组继续递归调用快排，并不划算。快排的递归调用和分区操作都有固定开销，而插入排序对接近有序的小数组极其高效，常数因子非常小。所以工业级排序实现里，通常会在数组规模低于某个阈值时切换到插入排序。

这个阈值到底取多少，各版本不完全一样。我实测过从8到32不等，阈值16左右效果相对均衡。注意这个参数不是越大越好：如果阈值太大，小数组全用插入排序，而插入排序对随机大数组是O(n^2)的，反而拖慢整体速度。

代码实现上，就是把递归版本的第一步判断改一下：

if right - left + 1 <= 16: insertion_sort(arr, left, right) return

插入排序的代码本身也很简洁，但要保证仅处理指定区间，不要越界：

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

光这个优化，我在10万元素的随机数组上实测，能带来15%到25%左右的性能提升。原因是减少了大量小规模递归的函数调用开销。

4.3 警惕特殊数据：重复元素过多的处理

如果数组里有大量重复元素，比如10万个元素全是同一个值，标准的Lomuto分区会退化成什么状态？每次分区基准值等于所有元素，扫描一遍后所有元素都堆到基准的同一侧，递归深度直接变成n，复杂度O(n^2)。这种数据在真实业务中完全可能碰到，比如用户状态字段的枚举值。

应对方案有三种：第一种是随机化基准，但这种情况下基准再怎么随机也都是同一个值，没有用；第二种是双指针从两端向中间扫描，让相等的元素尽量被交换到两侧对称的位置；第三种是使用三路分区，把等于基准值的元素集中到中间，完全不参与后续递归。

def partition_three_way(arr, left, right): pivot = arr[right] less = left greater = right i = left while i <= greater: if arr[i] < pivot: arr[less], arr[i] = arr[i], arr[less] less += 1 i += 1 elif arr[i] > pivot: arr[i], arr[greater] = arr[greater], arr[i] greater -= 1 else: i += 1 return less, greater

三路分区的核心维护三个区域：小于基准的区域、等于基准的区域、未扫描区域。less指向小于基准的边界，greater指向大于基准的边界，i遍历未扫描区域。每遇到一个小于基准的元素，就把它放进小于区；遇到大于基准的元素，就把它丢到大于区，且不推进i，因为换过来的元素还没有被检查过。

这个版本在处理大量重复元素的场景下，时间复杂度从接近O(n^2)直接拉回O(n log n)，而且等于基准的部分越多，实际性能越好。面试中如果被问到“如果数组中有大量重复元素，快排会不会退化”，能当场写出三路分区是非常加分的行为。

4.4 不得不知道的排序江湖：快排与TimSort、堆排的关系

快速排序不是万能的排序方案。工程实际中，很多语言内置的排序算法并不是单纯的快排，而是多种排序算法的组合。比如某些环境下的对象排序用的是归并排序的优化版本，某些环境下用的是双基准快速排序。这是考虑到稳定性和数据分布特征的综合选择。

快速排序不适合需要稳定排序的场景，因为分区过程会跨越式地交换元素，相同元素的相对顺序无法保证。如果业务上要求按多个字段连续排序，且后一个字段不能打乱前一个字段的相对顺序，你就需要稳定的排序算法。稳定性这个特性，归并排序天生具备，快速排序天生不具备。

那为什么快排还有如此高的地位？因为它平均性能好、原地排序省内存、缓存友好性佳。在大数据量、内存宝贵的服务器环境中，这些特性都极其值钱。世界上不存在一个绝对最优的排序算法，只有针对场景和约束的最合适方案。

5. 快速排序常见问题与排查实录

这里记录的是我实际写快速排序代码时踩过的坑，以及我帮别人排查过的典型问题。这些问题如果你不看，自己调试可能要花不少时间。

5.1 死循环问题：等号造成的分区失效

我最早写Hoare分区时，写出过一个死循环版本：

# 错误示例 while arr[i] < pivot: i += 1 while arr[j] > pivot: j -= 1

两个指针指向等于基准的元素时，不会进入内层循环，然后交换。如果两个指针都指向等于基准的元素，交换后两个值一模一样，指针没有前进，再次判断还是相等，再次交换，无限循环下去。解决办法是至少有一侧循环条件带等号，或者在交换后强制移动指针：

while arr[i] < pivot: i += 1 while arr[j] > pivot: j -= 1 if i >= j: break arr[i], arr[j] = arr[j], arr[i] i += 1 j -= 1

交换后强制移动指针，才能保证每次循环至少推进一格，循环必然结束。这个细节非常重要。

5.2 越界问题：递归边界没有收干净

Lomuto分区返回的基准位置pivot_index，处理左子区间时使用(left, pivot_index - 1)，右子区间使用(pivot_index + 1, right)。如果这里不小心把pivot_index本身又包含进去了，基准元素会被反复参与排序，不过由于Lomuto分区中基准在分区后已经在正确位置，再递归进去会导致逻辑错乱。更常见的问题是递归结束条件写错，导致空区间或单元素区间也继续递归，最终越界。

可以用一个极端小数据手工走一遍。比如数组[2, 1]，分区后基准位置返回0或1，左子区间或右子区间至少一个为空。你按代码逻辑推一遍，如果递归调用时传给了一个空区间且没有结束条件拦截，肯定就出界了。

5.3 性能退化时的定位方法

如果你实现的快排排序一个10万元素的随机数组需要好几秒，大概率是分区不均衡导致的。定位方法很简单：在递归函数入口打印当前区间的长度，观察打印出来的数值是否快速收敛到1。如果经常出现特别长的区间，说明基准选择策略有问题。

改用三数取中后，绝大多数场景下递归深度都会维持在接近log2 n的水平。对100万元素的数组，理想深度在20左右。如果递归深度显著超过这个值，就得检查基准选取了。

5.4 稳定性问题的实际案例

有个朋友做排行榜查询，要求相同分数的用户按注册时间升序排列。他直接用快排对分数排序，结果相同分数的用户顺序每次跑都不一样，后来换成稳定排序算法才解决。这不是快排的bug，而是它的特性决定的。分区过程中的元素交换是无规则跨越式的，两个相同分数的用户，谁先被交换到前面完全是随机的，和它们在原始数组中的先后顺序没有固定关系。

所以当你明确需要稳定性时，不要硬用快排。快速排序的原则是“不保证稳定”，这与归并排序有本质区别。认清算法的边界，避免强行使用，是合格开发者的基本素质。

5.5 一个容易忽略的问题：对称但不等价的边界写法

网上很多快排代码，看起来只有一两行的差别，但如果分区实现不同，递归边界是完全不能互换的。某天你看到一段Hoare分区代码，它返回的索引不是基准的最终位置，而是一个分界点，比如所有小于等于基准的元素都落在左半部分，大于等于基准落在右半部分。此时递归就不能用pivot_index - 1和pivot_index + 1来切分，因为基准可能就在分界点附近，但并没有确定落到某一个固定位置。

这种代码有两种常见处理：

quicksort(arr, left, pivot_index) quicksort(arr, pivot_index + 1, right)

或者

quicksort(arr, left, pivot_index - 1) quicksort(arr, pivot_index, right)

区别取决于分区实现返回的到底是“左侧最后一个小于等于基准的位置”还是“右侧第一个大于等于基准的位置”。如果你从网上复制了一个分区函数，却没注意它配套的递归边界写法，那十有八九会死循环或越界。我建议你选定一个版本后，用[5, 2, 3, 1, 4]这样的数据，把分区过程每一步都打印出来，自己走一遍，彻底吃透这个版本再迁移。

6. 双基准快速排序：站在巨人的肩膀上看快排

最后再扩展一个工业级方案。某些成熟的排序库中，采用的不是单基准快排，而是双基准快速排序。它选取两个基准p1和p2，p1小于p2，分区后数组被分成三块：小于p1、介于p1和p2之间、大于p2。然后对三块区域分别递归排序。

双基准的优势在于：每轮分区后，两个基准值都已经就位，而且数组被分成三段，递归时的子问题更小。当数据随机分布时，双基准快排平均比较次数比单基准更少，对缓存也更加友好。但它的实现复杂度明显更高，两个基准的选取、三指针的移动、各种边界判断写起来非常容易出错。

如果你已经能把单基准快排的自选基准、分区、递归边界都讲清楚，理解双基准就是水到渠成的事。面试时主动提到双基准快排的存在和大致思路，能体现你对排序算法的横向视野，这是加分项。但日常手写代码，不建议首选双基准来表达，毕竟在45分钟内写一个正确无误的双基准实现，比自己浪费时间要重要得多。

快速排序这个题目看起来简单，但它能同时考察编码基本功、边界条件思维、复杂度分析和实际工程优化意识，所以深度非常够。我自己每次重新实现快排，都能发现之前忽略的细节，这种“越写越有意思”的感觉，也许就是算法的魅力所在。

最后分享一个小习惯：我写完任何排序算法的第一件事，不是拿大数组测性能，而是拿[5, 4, 3, 2, 1]、[1, 1, 1, 1]、[1]这种极端小数组手动跑一遍，确认边界逻辑没问题。这能省下后面大量调试时间。你在自己练习的时候，也可以按这个思路建立一套快速自检流程。