企业官网建设流程全解析

快速排序是数据结构课程里“性价比”很高的一个算法：代码量不大，思想深刻，实际表现又强，面试和项目里都常碰。但很多新手学到“快速排序”往往只学到外壳，一旦要自己写，或者要把它用到工程里，各种边界问题就全冒出来了：基准值选在头上导致有序数组直接退化、递归太深爆栈、重复数据多的时候快排慢成渣、排序后相对顺序乱了才发现不稳定带来的麻烦。这篇文章我想根据自己的实践，把快速排序从原理到经典优化完整梳理一遍，包括分区到底怎么写、基准值怎么选、什么时候切换成插入排序、重复元素多了怎么处理、递归爆栈怎么办、非递归怎么写。适合三类人看：刚学完基础还没自己完整实现过一遍的初学者，准备面试想理顺细节的人，以及工作中需要手写排序但又不想直接抄内置函数的工程师。

1. 快速排序的核心思想与基础实现

1.1 先理解分治：排序问题如何被拆解

快速排序用的分治思路，一句话概括就是：选一个基准值，把数组拆成“比基准小的一堆”和“比基准大的一堆”，然后对这两堆分别做同样的操作，直到每个子区间只剩一个元素或空区间。这个思路听起来简单，但和归并排序有本质区别。

归并排序是“先拆到底，再边合并边排序”，真正让数据有序的动作发生在归并阶段，也就是说它在合并时要额外申请临时数组。快速排序则相反，它在拆解阶段就通过“分区”把元素放到了正确的一侧，而基准值也被放到了最终位置，等到递归完成时数组已经原地有序，不需要额外的合并步骤。这就是为什么快速排序可以做到 O(1) 的额外辅助空间（忽略递归栈），归并排序却要 O(n) 的空间。

把这个拆解动作做得越干净，后续递归承担的任务就越少。分区之后，左子区间里的所有元素都小于基准值，右子区间里的所有元素都大于基准值，基准值不用再参与排序。问题规模从 n 变成了两个约 n/2 的子问题，这就是高性能的来源。

实际写代码的时候，很多人会忽略一个重要细节：分区的返回值到底指向哪里，递归边界该怎么设。不同分区方法返回的索引含义不一样，递归区间也跟着变，这一步如果不搞清楚，后面写出来的代码不是在边界上死循环，就是把某个元素漏掉。后面第 2 节我会专门讲这个坑。

1.2 基准元素与分区过程

分区是整个快速排序的核心，也是所有优化手段的落脚点。我自己初学时的感受是：递归那部分只要理解了，写出来并不难，真正容易出问题的全在 partition 函数里。

常见的基础实现有两种写法。第一种是“单向扫描”方式，思路很好懂：选最后一个元素当基准，维护一个“已处理区”，从左往右扫，遇到小于等于基准的元素就把它交换到已处理区末尾，扫描结束后把基准放到已处理区后面。这种写法交换次数比较清晰，但等号处的细节很容易踩坑。

第二种是“双向扫描”方式，效率更高，也更接近工程实现：左右各一个指针，左指针找大于等于基准的元素，右指针找小于等于基准的元素，找到就交换，直到两个指针交错。单次交换能让两个元素同时归位，所以比较和交换次数更少。双向扫描的等号处细节也一样重要，处理不好会导致基准被挪来挪去，甚至出现某个子区间为空的情况。

我强烈建议初学者把这两种分区都各写一遍，然后跑各种极端数据对比。分区没写对，后面所有优化都是在错误的地基上盖楼。

1.3 基础版递归实现

先用最容易理解的单向扫描方式写一版，语言我用 Python 演示。

def quicksort(nums, left, right): if left >= right: return p = partition(nums, left, right) quicksort(nums, left, p - 1) quicksort(nums, p + 1, right) def partition(nums, left, right): pivot = nums[right] i = left - 1 for j in range(left, right): if nums[j] <= pivot: i += 1 nums[i], nums[j] = nums[j], nums[i] nums[i + 1], nums[right] = nums[right], nums[i + 1] return i + 1

这一版逻辑最直白，适合教学，但不是工程最优选择。因为每次扫描都把“小于等于基准”的元素交换到前面，如果数组里大量元素等于基准，这些等值元素会全挤到一侧，破坏平衡，最坏情况下会退化到 O(n^2)。所以后面 3.3 节要讲三向切分来解决重复元素问题。

再补充一版双向扫描的分区实现，这版在工程中更常见：

def partition_dual(nums, left, right): pivot = nums[(left + right) // 2] i = left - 1 j = right + 1 while True: i += 1 while nums[i] < pivot: i += 1 j -= 1 while nums[j] > pivot: j -= 1 if i >= j: return j nums[i], nums[j] = nums[j], nums[i]

注意这版返回的 j 不是基准的最终位置，而是“左右分界点”。递归时要用两段区间[left, j]和[j+1, right]，不能照搬单向扫描那版的递归写法。很多网上流传的代码拼接错位，就是因为没注意到两种分区返回值的语义不同。

2. 快速排序的效率边界与复杂度拆解

2.1 最好、最坏、平均情况到底怎么算

很多人记住“快速排序平均 O(n log n)”，但不知道这个结论成立的前提。我建议亲手推一遍，这样才能理解为什么基准值选择能成为优化重点。

最好情况是每次分区恰好把数组分成两个等长的子区间。递归过程形成一棵完全平衡的树，每层的分区代价是 O(n)，树高是 log n，所以总复杂度是 O(n log n)。

最坏情况是每次分区都极度不平衡，比如基准值恰好是当前区间的最小值，那么右子区间的长度是 n-1，左子区间为空。递归退化成一条链，每层都要扫描近似 n 个元素，总比较次数是 n + (n-1) + (n-2) + ... + 1，也就是 O(n^2)。这种退化不是只存在于理论里：直接用第一个或最后一个元素当基准，然后排序一个已经有序或逆序的数组，实测就能看到运行时间呈抛物线增长。

平均情况的分析比较复杂，数学功底好的可以去看经典推导；不想看推导的话，只要记住结论：在随机分布的输入下，快速排序的表现非常接近 O(n log n)，而且常数系数比其他分治排序小，实际运行往往更快。这也是名字叫“快速”的原因。

我做过一个粗糙实验：用一百万随机整数，分别跑冒泡、归并、双向扫描快排，归并大约需要几百毫秒，快排能节省三成左右时间，而且不占用额外大块内存。当然这个数据在不同语言和机器上会变，但趋势基本一致。

2.2 稳定性辨析：为什么快速排序不稳定

稳定性这个概念在很多业务场景里很重要。假设有一批订单先按金额排序，再按时间排序，如果排序算法是稳定的，第二次排序后，相同时间的订单内部还会保持金额的先后顺序。如果不稳定，相同时间内的顺序可能被打乱。

快速排序是不稳定的。原因在于分区时会远距离交换元素，可能把相等元素的相对顺序弄反。举个例子：数组[a1, a2, a3]表示三个值相同的元素，它们在原始顺序中是 a1、a2、a3，经过一次分区，基准或相等元素可能被交换到别的区间，a1 和 a3 的位置对调，相对顺序就变了。

如果你确定业务依赖相同关键字之间的原始顺序，就不要用快速排序，或者给比较函数增加一个带唯一粒度的“次要关键字”，比如把对象 ID 也纳入比较，人为保证排序的确定性。这一点是快排在工程上需要特别注意的。

2.3 递归深度与栈开销：有序数据的栈溢出风险

递归快排的栈开销取决于递归深度。最好情况下递归深度是 log n，一百万元素深度也就二十层左右，毫无压力；最坏情况下深度是 n，一百万元素就可能在某次递归调用中压入几十万层栈帧。

而且这种最坏情况在现实中很常见：数组本来就已经排好序或近似有序时，如果基准取首个或末尾元素，分区出的两个子区间一个为空，另一个长 n-1，递归深度直接逼近 n。我见过不少项目在数据量只有几万的时候就崩溃或响应极慢，查到最后就是这种“有序数据 + 固定基准”组合造成的。

解决办法有两条路线：一条是改进基准值选取，让分区尽量平衡，属于从根源上规避；另一条是把递归改成显式栈循环，属于物理上绕开调用栈深度的限制。两条路线不算冲突，工程上经常同时用，后面第 3、4 节展开讲。

下面用一个表格把快排的复杂度边界汇总清楚：

3. 快速排序的经典优化策略

3.1 基准值选取：三数取中与随机化

针对“固定基准遇上非随机数据会退化”的问题，最直接的优化是改进选基准的方式。

第一种是随机化：从当前区间随机挑一个元素当基准。这不能保证每次分区都平衡，但能让“每次都不平衡”的概率变得极低。尤其对于输入数据是近乎有序的情况，加入随机化后，退化成 O(n^2) 的概率可以忽略不计。代价是需要随机数开销，而且随机数生成器本身有成本。

第二种是“三数取中”：从当前区间的左端、中间、右端各取一个元素，选其中值大小居中的那个当基准。这种做法的好处是能直接避开有序数据的坑：数组基本有序时，最左、最中、最右三个位置的值中间的那个通常很接近整个区间的中间值，分区自然平衡。代码上可以在 partition 之前先做一个三数排序交换，把基准挪到区间的某个固定位置，然后复用原有分区逻辑。

我自己的习惯是优先上三数取中，数据规模特别大、或者担心输入存在恶意分布时再加随机化。三数取中代码量不大，对性能的提升却非常明显。

3.2 小区间切换插入排序

另一个容易被忽略的优化是“小区间到底递归不递归”。分区是一个 O(n) 操作，但它有固定开销：函数调用、比较、交换、划分边界。当子区间长度很小的时候，这个固定开销占比就显得很高，继续递归不划算。

工程里常见的做法是设置一个阈值，比如区间长度小于等于 16 时，直接改用插入排序。插入排序在小数据集上的实测表现往往优于快排，因为它的循环很简单，对缓存友好，而且小数据本身接近有序的概率大，插入排序对这种“几近有序”的小片段尤其快。

这个阈值没有唯一标准。我在常用语言里测试下来，8 到 24 之间差异不大，取 16 是个比较稳妥的默认值。不要把它设得太大，比如 100 甚至更多，否则大量小片段都走 O(n^2) 的插入排序，整体性能反而会被拖慢。

混合思路的代码结构大致是这样：

def quicksort_mixed(nums, left, right): if left >= right: return if right - left + 1 <= 16: insertion_sort(nums, left, right) return p = partition_dual(nums, left, right) quicksort_mixed(nums, left, p) quicksort_mixed(nums, p + 1, right)

示意图里的插入排序函数就是普通的插入排序，只是限定在[left, right]区间内工作。

3.3 三向切分处理重复元素

数组里存在大量重复元素时，普通双向分区会怎么表现？想象一个百万级数组，里面只有 1 和 2 两种值。双向扫描虽然把小于基准和大于基准的元素分开，但等于基准的元素会左右各占一堆，导致两边的分区结果仍然很长，递归次数没有显著减少，处理重复元素时做了大量无效交换。

荷兰国旗问题式的三向切分是经典解法：一趟分区把数组切为三个区域，分别存放“小于基准”“等于基准”“大于基准”的元素。等于基准的区域一次性归位，后续递归不再触碰，相当于把重复元素直接压缩掉了。

def quicksort_3way(nums, left, right): if left >= right: return lt, i, gt = left, left + 1, right pivot = nums[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_3way(nums, left, lt - 1) quicksort_3way(nums, gt + 1, right)

这段实现里，lt指向小于区的右边界，gt指向大于区的左边界，i是当前扫描位置。等于基准的元素就被夹在[lt, gt]中间，不再参与递归。这个优化对“大量重复值”的输入效果非常显著。如果数据里重复值不多，三向切分的额外判断会略微增加常数开销，所以我不是所有场景都用它，而是根据数据特征决定。

4. 非递归实现与其他工程化改造

4.1 用显式栈替代递归：防止调用栈爆掉

递归快排的栈深度不稳定，最坏情况下和数组规模呈线性关系。在递归深度受限的语言或平台里，比如某些嵌入式环境或函数调用深度受限制的场景，直接递归很容易触发栈溢出。

一种稳妥的方案是自己维护一个栈，把待处理的区间存进去，循环弹出处理。这样做的好处是栈占用可以控制，且不会因为递归调用层级太多而崩溃。

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

这里有一个小小的优化细节：总是先把较大的区间压栈，再压较小的区间，这样循环弹出时会先处理较小的区间。为什么这么做？因为较大的区间虽然晚处理，但它被保存在栈里的时候不会导致栈无限制膨胀，整体栈的大小可以被压到 O(log n) 的级别。这个技巧在很多避免递归深度的实现里都用得到。

用显式栈代替递归还有个额外好处：你想在排序中途做“限流”或“暂停恢复”时会更容易，因为状态完全在一个栈对象里，可以随时停下来观察。

4.2 用循环改写单侧递归，减小递归深度

如果并不想彻底放弃递归写法，还有一个折中策略：只递归处理较小的一侧，较大的一侧用循环继续在当前函数内处理。

这种方法在不少教科书里叫“尾递归优化”，但准确说是“限制递归深度”的手段。它把递归深度从可能达到 n 降低为 O(log n)，同时又比显式栈更轻量。

def quicksort_tail(nums, left, right): while left < right: p = partition(nums, left, right) if p - left < right - p: quicksort_tail(nums, left, p - 1) left = p + 1 else: quicksort_tail(nums, p + 1, right) right = p - 1

这个写法要稍微想一下：每次只递归小区间，大区间进入下一轮 while 继续分区，这样函数调用栈里永远只会同时存在一条较短的调用链。结合三数取中、插入排序阈值之后，这个版本基本达到了比较接近工程级快排的水平。

4.3 工程中排序选型到底怎么取舍

讲到这里，难免会有人问：既然快排还能优化，为什么很多语言内置的排序函数不直接用纯快排？

我的理解是：工程上的排序选型从来不是只盯一个算法的理论复杂度，而是在最坏情况、稳定性、常数开销、数据分布不确定等多重目标之间找平衡。很多内置排序实际上是“混合排序”：数据量小时用插入排序，稍大时用快排，并且通过内省式检测，如果递归深度超过某个阈值就切换到堆排序。这样既保留快排的平均高性能，又保证最坏情况不会退化到 O(n^2)。

所以在实际项目里，我的建议很直接：

• 绝大多数场景，直接用语言内置排序函数，它已经包含了很多优化。
• 只有当你明确知道数据特征，或者内存访问路径有特殊要求时，才考虑手写排序。
• 手写时至少把三数取中、小区间插入、三向切分这类常见优化做进去，否则不如内置函数。
• 需要稳定排序、且需要手写时，优先考虑归并排序而不是快排。

5. 实战排错与排序算法学习的一些经验

5.1 常见问题速查表

我在手写快排和给模拟项目X的数据预处理模块加固排序环节时，反复踩过几个坑。整理成一张速查表，方便对照：

5.2 一个最容易忽略的分区边界坑

开头说“分区返回值语义不同”，这里展开讲。用单向扫描那版，分区的返回值是基准值的最终下标，所以左右子区间是[left, p-1]和[p+1, right]。用双向扫描那版，返回值是左右指针交错的位置，基准不一定在这个位置，所以递归区间是[left, p]和[p+1, right]。

很多把网上代码粘到项目里的人，会发现排序后某些元素顺序不对，原因就是两版代码混用。我自己一开始也没少在这一步吃亏。调试方法很简单：在排序前后分别打印数组，如果发现“小的在大的后面”，就先确认递归区间和分区返回值的匹配关系。

还有一种隐蔽问题：单向扫描分区时用<=还是<会影响相等元素的分布。<=会把相等元素扫到左侧，<会扫到右侧，如果基准又被放到某一侧，可能让子区间长度失衡。平时看不出问题，但极端重复数据下就很容易触发退化。

5.3 我是怎么检验排序算法写对没写对的

疯狂写几个测试用例并不够，因为你验得再多也只是一部分样本。我建议至少要覆盖这么四类：

• 空数组和单元素数组，这一类直接返回，不该报错。
• 完全有序、完全逆序的数组，主要用于暴露基准值退化问题。
• 大量重复元素的数组，比如几万个 1 和 2 混在一起，专门测三向切分。
• 随机大数组，用来对比不同实现的实际运行时间。

除功能测试外，我还习惯在代码里埋一个计数器统计比较次数和交换次数。同一个输入，不同优化版本跑出来的计数差异会非常明显，比只靠计时器更稳定，也不受系统负载影响。这个习惯帮我快速判断一个理论上的优化是否真的有效。

5.4 几个我常用的学习顺序建议

如果是对快排还不太熟的读者，我建议按这个顺序练：先写递归 + 单向分区，确保理解分治和基准；再改成双向分区，理解两种分区返回值差异；然后加三数取中和插入排序阈值；接着加三向切分；最后如果项目有限制，再把递归改成显式栈循环。每改一步，都用上一节的测试用例集跑一遍。

这串流程走完，不夸张地说，你对快速排序的理解已经超过绝大多数只会调内置排序的人。实际调试时如果再有疑问，可以把暂停回目录翻看这篇，应该能解决大部分问题。

我在实际使用中最大的体会是：快速排序并不是一个“背代码”的算法，它更像一个实验场，让你理解基准、分区、递归这几件事是怎么耦合的。优化策略看着多，但本质上都在做同一件事：想办法让每次分区尽量平衡，同时减少不必要的比较和交换。把这些想明白了，不管未来换哪种语言，拿过来十几分钟就能写出一个靠谱的快排。