1. 先把思路摊开：交换排序到底在解决什么事

排序算法里，交换排序是最好理解也最容易被轻视的一类——冒泡排序和快速排序都靠"比较 + 交换"这两个动作，把序列里的逆序一点点磨平。很多人写冒泡排序就是十几行代码一交了事，快速排序背个模板就往题目里套。可真要把它们写对、写稳、写得能应付各种脏数据，同一个分区函数能写出三种细节差异极大的版本，递归改非递归又是一处翻车高发区，碰上大量重复元素还得请出三路划分。这篇就把这块内容从头到尾捋一遍：三种递归分区写法各自的边界条件、显式栈版非递归快排怎么把栈深度压到 O(log n)、三路划分以及三路归并在什么数据上才值得用。

先说一个贯穿全文的概念——逆序对。序列里如果 i < j 但 a[i] > a[j]，这一对数就是逆序对。一个序列有多"乱"，本质上就看逆序对有多少：完全有序是 0 对，完全逆序是 n(n-1)/2 对。冒泡排序每交换一次相邻元素，逆序对数量恰好减 1，一次都不会多减，所以它在近乎有序的数据上极快，在逆序数据上极慢，快慢的根源就在这里。快速排序的思路完全不同：一次分区能把一个元素送到它的最终位置，同时把大量元素按"比基准大还是小"分到两边，一次性消掉 O(n) 量级的逆序对，再递归处理两半，平均下来就是 O(n log n)。

这三种递归写法、非递归写法和三路划分，解决的其实是三个不同层面的问题。三种递归写法解决的是"分区这一步怎么写才不出错、常数才小"；非递归解决的是"递归栈深了会爆"；三路划分解决的是"数据里重复元素太多，朴素分区会被打回 O(n^2)"。把这三个层面分开看，比把它们混在一起背模板要清楚得多。刚接触数据结构的同学可以照着文中代码直接抄，工作几年、面试前想再顺一遍的人，后面"踩坑实录"和"实测"两节应该更有参考价值。

1.1 一次分区能顶冒泡一整轮，原因在不变式

快速排序的核心不是递归，是分区函数。分区函数要做的事情只有一件：选定一个基准值 pivot，把区间重新排列成"左边都不大于 pivot、右边都不小于 pivot、pivot 落在最终位置上"这三段。这个约束叫做分区不变式，只要它成立，递归把左右两半各自排好，整个数组就有序了。

冒泡排序一轮下来只能保证末尾一个元素到位，代价是比较 n 次、交换若干次；分区一趟也是扫描一遍区间，但它保证的是"一个元素到位 + 两侧元素全部按大小分流"。这个"分流"就是快排比冒泡快一个量级的全部秘密。也正因为如此，分区函数写错一个不等号，整个算法的正确性就没了，而这种错误在小数据上往往还测不出来——比如只有 3 到 5 个元素的数组，很多边界错误恰好看不出问题，一定要用 20 个以上的随机数据反复对拍才能暴露。

另一个必须提前说清的点是稳定性。交换排序天然不稳定，因为交换动作会跨越中间元素，把原本相等的两个元素的相对次序打乱。如果你有"按第一关键字排完再按第二关键字排"这类需求，快排和冒泡都不是好选择（冒泡其实稳定，但它太慢），该上归并。这个结论在后面三路归并那节还会再提一次。

1.2 三个痛点，对应三套实现

我习惯把这块内容按痛点来组织，而不是按教材目录来组织。痛点一是分区怎么写：左右指针法、挖坑法、前后指针法，三者的骨架完全一样，差别只在"基准元素存在哪、指针往哪边走、什么时候交换"，但就是这些差别决定了代码好不好写、常数大不大、对重复元素友不友好。

痛点二是递归深度。快排的递归层数平均是 log n，最坏是 n。n = 100 万时最坏情况就是 100 万层，函数调用栈根本扛不住，程序直接崩。这不是理论问题，一段已经升序的数据送进去，取首元素当基准的朴素快排就会一路退化，栈溢出几乎是必现的。

痛点三是重复元素。分区时用严格大于、严格小于做判断，一堆相等的元素会被全部分到同一侧，每层只能削掉一个元素，复杂度退化成 O(n^2)。现实数据里重复值极常见（比如按城市、按状态码排序），三路划分就是专门为这种情况准备的：一趟分区直接切成"小于、等于、大于"三块，等于区不用再递归。

1.3 我自己的选择顺序

实际写代码时我的判断顺序是这样的：数据量小于 32 这种量级，直接插入排序，别犹豫，快排的递归开销和分支预测失败在这个规模上完全不划算；数据量中等且基本有序，插入排序或者带提前退出优化的冒泡都行；数据量大数据随机，快排配三数取中；重复值多，直接上三路划分；要求稳定，归并；内存受限、不允许额外 O(n) 空间，还是快排。这个判断顺序不是背出来的，是踩过几次坑之后形成的条件反射，后面每一节都会给出一条对应的理由。

2. 冒泡排序：老古董里藏着两个真正有用的优化

冒泡排序的原始版本没什么可讲的：外层循环控制轮数，内层循环从头到尾比较相邻两个元素，逆序就交换。第 i 轮结束后，末尾 i 个元素已经就位，所以内层循环的上界可以逐轮收缩。这个版本的时间复杂度是固定的 O(n^2)，不管数据本来有没有序，一趟都不会少跑。

真正有价值的是两个优化，它们把冒泡从"教学演示"变成了"小数据和近乎有序场景下真的能用"的算法。第一个是提前退出：如果某一轮从头到尾一次交换都没发生，说明整个序列已经有序，直接 break。加上这个判断之后，最好情况（输入本来有序）退化成 O(n)，只需要一趟扫描。这是冒泡排序唯一一个能拿得出手的复杂度结论，也是很多面试题里"如何判断数组是否已排序"的标准答案。

void bubbleSort(int a[], int n) { for (int i = 0; i < n - 1; ++i) { bool swapped = false; for (int j = 0; j < n - 1 - i; ++j) { if (a[j] > a[j + 1]) { std::swap(a[j], a[j + 1]); swapped = true; } } if (!swapped) break; } }

注意内层判断用的是>而不是>=，这一个符号决定了冒泡排序是稳定的：相等元素不会触发交换，相对次序得以保留。这一点经常被忽略，但它是冒泡在稳定性上优于快排的唯一理由。

2.1 记录最后一次交换位置，把边界一次收到底

第二个优化更巧妙，收益也更实在。既然第 i 轮之后末尾 i 个元素有序，那能不能一次收缩得更多？可以。记录本轮最后一次发生交换的位置lastSwap，这个位置之后的元素在本轮里都没有再参与交换，说明它们已经局部有序，下一轮的右边界直接从 lastSwap 开始，不用再扫。

void bubbleSortV2(int a[], int n) { int end = n - 1; while (end > 0) { int lastSwap = 0; for (int j = 0; j < end; ++j) { if (a[j] > a[j + 1]) { std::swap(a[j], a[j + 1]); lastSwap = j; } } end = lastSwap; } }

这个版本在"尾部已经有序、只有头部少量元素乱序"的数据上效果非常明显。举个具体例子：一个长度 10 万的数组，末尾 9 万个元素已经升序，只有前 1 万个是乱的。原始冒泡要跑接近 10 万轮，每轮平均扫描 5 万次，加起来是几十亿次比较；加了 lastSwap 之后，第一轮扫完 lastSwap 大约停在 1 万的位置，第二轮边界直接缩到 1 万，后面的 9 万个元素一次都不会再被访问。这个差距不是常数级的，是数量级的。

不过话说回来，同样的数据用插入排序会更舒服。原因在于交换的代价：冒泡每次交换要做三次赋值（swap内部是 temp + 两次赋值），插入排序是把元素往后挪一位，一次赋值就够。近乎有序时两者的比较次数都是 O(n)，但冒泡的赋值次数是插入排序的三倍左右。实测下来，10 万规模的近乎有序数组，插入排序通常比带 lastSwap 优化的冒泡快 2 到 3 倍。所以我的结论是：冒泡的两个优化值得懂，值得会写，但真到选型时，小数据和近乎有序场景优先插入排序，冒泡只在"必须稳定 + 数据量极小 + 代码要短"这种边角需求里出现。

2.2 冒泡真正还活着的几个场景

第一个场景是教学和面试。冒泡排序的代码足够短，短到可以在白板上边写边讲清楚"为什么第 i 轮之后末尾 i 个有序"这个不变式。讲清楚了不变式，后面讲快排的分区不变式会轻松很多。

第二个场景是链表上的值交换。数组上冒泡要频繁访问 a[j] 和 a[j+1]，链表上没法随机访问，但如果你只是想交换节点的值而不动指针，冒泡的相邻访问模式反而和链表很搭——一趟遍历就是沿着 next 指针走。当然链表排序的正经做法是归并，这里只是说冒泡在链表上不会像快排那样别扭。

第三个场景是"一次扫描判断有序性"。很多业务代码里需要判断一份数据是不是已经排好序，这时候不需要完整排序，跑一趟冒泡的提前退出逻辑就够了，代码只有几行，比调用一个通用排序再逐项比对要清爽。

提示：不要在被反复调用的热路径里用冒泡处理上千级别的数据。n = 5000 时冒泡大约是 1250 万次比较，看着不多，但如果这段代码每秒被调用几十次，累积起来的耗时会让整个服务变慢。这种问题排查起来特别费劲，因为单次耗时很小，性能剖析工具上一闪而过。

3. 快速排序的三种递归实现：同一个骨架，三种交换手法

三种递归写法的共同骨架是：选基准、分区、递归两半。差别全在分区函数里。我把它们分别叫左右指针法、挖坑法、前后指针法，这三个名字在不同教材里可能有细微出入，但看代码就能对上号。下面每个版本我都会给完整代码加一次手工推演，因为分区函数的错误几乎都藏在"指针谁先走""循环条件带不带等号"这类细节里，光看代码看不出来。

3.1 左右指针法：双指针从两端往中间夹

左右指针法的做法是：取区间左端元素作为基准值（存在变量里），左指针 i 从左往右找比基准大的，右指针 j 从右往左找比基准小的，找到就交换，直到两个指针相遇，最后把基准值和相遇位置的元素交换。

int partitionHoare(int a[], int l, int r) { int pivot = a[l]; int i = l, j = r; while (i < j) { while (i < j && a[j] >= pivot) --j; // 右指针先走 while (i < j && a[i] <= pivot) ++i; if (i < j) std::swap(a[i], a[j]); } std::swap(a[l], a[i]); return i; }

这段代码最关键的一行是注释那句"右指针先走"。为什么必须右边先走？因为最后swap(a[l], a[i])要把基准放到相遇点 i 上，而基准原本在最左端，它左边的所有元素都必须不大于基准。只有当右指针先动，相遇点才一定落在"不大于基准"的那一侧。

不亲眼看到出错，这个理由很难记住。拿数组[1, 5, 3]走一遍错误版本：基准 pivot = 1，如果先动左指针，a[0] = 1 <= 1 所以 i 前进到 1，a[1] = 5 > 1 停下；再动右指针，a[2] = 3 >= 1 所以 j 退到 1，i == j 循环结束。最后交换 a[0] 和 a[1]，数组变成[5, 1, 3]，基准 1 落在位置 1，但它左边是 5，比它大，分区不变式被破坏。递归下去左边那一半永远排不对。

再用正确版本走一遍[3, 1, 4, 2, 5]：pivot = 3，i = 0, j = 4。右指针找小于 3 的，a[4] = 5、a[3] = 2 停，j = 3；左指针找大于 3 的，a[0] = 3、a[1] = 1、a[2] = 4 停，i = 2；i < j，交换 a[2] 和 a[3]，数组变[3, 1, 2, 4, 5]。继续，j 从 3 出发，a[3] = 4 >= 3 退到 2，此时 i == j == 2，退出循环。交换 a[0] 和 a[2]，得[2, 1, 3, 4, 5]，基准 3 在位置 2，左边 [2, 1] 全小于 3，右边 [4, 5] 全大于 3，分区正确。

这个版本的一个隐藏优势是：它用>=和<=做停指针判断，相等元素会被停在原地并参与交换，所以面对全相同元素的数组时，两边会均匀分开，递归深度是 O(log n)。这不是所有写法都有的性质，后面讲前后指针法时会看到反例。

3.2 挖坑法：用赋值代替交换

挖坑法的思路是把基准元素"挖走"，原位置变成一个坑，然后拿右指针找到的小元素填进坑里，坑的位置移到右边；再拿左指针找到的大元素填进新坑，坑又移回左边；最后把存在变量里的基准值填进最后的坑。

int partitionHole(int a[], int l, int r) { int pivot = a[l]; int i = l, j = r; while (i < j) { while (i < j && a[j] >= pivot) --j; a[i] = a[j]; // 填坑，坑移到 j while (i < j && a[i] <= pivot) ++i; a[j] = a[i]; // 填坑，坑移回 i } a[i] = pivot; // 基准归位 return i; }

拿[3, 1, 4, 2, 5]走一遍：pivot = 3，坑在 0 号位。右指针从 4 出发，a[4] = 5、a[3] = 2 停，把 2 填进 0 号坑，数组变[2, 1, 4, 2, 5]（注意 3 号位现在是脏的，但它马上会被覆盖），坑变成 3 号位。左指针从 0 出发，a[0] = 2、a[1] = 1、a[2] = 4 停，把 4 填进 3 号坑，数组变[2, 1, 4, 4, 5]，坑变成 2 号位。此时 i == j == 2，循环结束，把 pivot 填进 2 号坑，数组变[2, 1, 3, 4, 5]。结果和左右指针法完全一致。

挖坑法的实际收益在于减少了交换次数。左右指针法每次交换是三次赋值，挖坑法每次填坑是一次赋值，随机数据下交换次数大约是 n/6 量级，省下来的赋值对大体量数据是有感知的。代价是可读性稍差，因为中间过程中数组里会出现重复值（脏数据），调试时看到这种中间态容易怀疑自己写错了。我的建议是：面试手写优先左右指针法，好解释、好验证；工程里写快排工具函数用挖坑法，那点性能差异在百万级数据上是能测出来的。

3.3 前后指针法：单向扫描，逻辑最不容易写错

前后指针法放弃了从两端夹击，改成一遍从左到右的单向扫描。用一个 slow 指针维护"已处理区域里不大于基准的元素"的边界，fast 指针负责扫描。fast 遇到小于基准的元素，就和 slow 位置交换，slow 前进一位。

int partitionTwoPointer(int a[], int l, int r) { int pivot = a[r]; // 以最右元素为基准 int slow = l; for (int fast = l; fast < r; ++fast) { if (a[fast] < pivot) { std::swap(a[slow], a[fast]); ++slow; } } std::swap(a[slow], a[r]); return slow; }

这个版本的好处是循环条件简单到几乎不可能写错：只有一个 for 循环，没有内层 while，不存在"指针谁先走"的问题，也不存在指针越界的风险。手写代码时它的正确率是最高的，这一点在面试场景里价值很大。

但它有一个必须警惕的退化风险：基准取最右元素时，如果输入已经升序，a[fast] < pivot永远成立，slow 一路跟着 fast 走，最后swap(a[slow], a[r])交换的是自己，分区结果是左边 n-1 个、右边 0 个，递归深度直接变成 n。10 万规模的升序数组就能把栈打穿。所以用前后指针法必须配随机化或三数取中，这不是可选项，是必选项。相比之下左右指针法在升序数据上虽然也会退化，但因为两侧同时推进，实际表现会稍好一点，但同样不能裸奔。

再补一句重复元素的问题：这个版本用的是严格小于<，所有等于基准的元素都会被甩到右边，全相同数组照样退化成 n 层递归。这就是三路划分存在的理由，第 5 节会详细说。

3.4 三种写法的对照与选型

三者的平均时间复杂度都是 O(n log n)，最坏 O(n^2)，空间都是 O(log n) 的递归栈。选型建议：手写和面试用左右指针法或前后指针法，讲得清楚；追求常数用挖坑法；任何版本都必须加三数取中或随机化。

// 三数取中：把中位数换到 l 位置，返回中位数下标 int medianOfThree(int a[], int l, int r) { int mid = l + ((r - l) >> 1); if (a[l] > a[mid]) std::swap(a[l], a[mid]); if (a[l] > a[r]) std::swap(a[l], a[r]); if (a[mid] > a[r]) std::swap(a[mid], a[r]); return mid; // 此时 a[mid] 是三者的中位数 }

mid = l + ((r - l) >> 1)这个写法比(l + r) / 2稳，因为 l 和 r 都接近 int 上限时后者会溢出成负数，进而导致数组越界。这个坑在 LeetCode 那种小数组上永远遇不到，在真实业务里数组下标接近 21 亿时就会炸，属于典型的"测不出来但会出事"的写法。

4. 非递归实现：用显式栈把递归挪出来

递归版快排的栈帧消耗是每个递归调用一帧，平均深度 log n，最坏 n。一般的默认栈大小是 8MB 左右，一帧几十字节，理论上能撑十几万层，但实际加上局部变量、调试信息、编译优化差异，几万层就可能崩。更麻烦的是崩的时候通常没有有意义的报错，就是进程直接没了，排查方向都找不到。

改非递归的思路很直接：递归版里保存现场靠的是函数调用栈，那我自己用一个std::stack存区间，效果完全一样。

4.1 栈里存什么，出栈顺序怎么定

栈里存的是待处理区间的左右端点，用pair<int,int>就行。流程是：初始把[0, n-1]压栈，然后循环——出栈一个区间，如果区间长度小于等于 1 就跳过，否则分区，把分出来的左右两个子区间压栈。

void quickSortIter(int a[], int n) { if (n <= 1) return; std::stack<std::pair<int,int>> st; st.push({0, n - 1}); while (!st.empty()) { auto range = st.top(); st.pop(); int l = range.first, r = range.second; if (l >= r) continue; // 空区间或单元素，直接跳过 int p = partitionHoare(a, l, r); st.push({l, p - 1}); st.push({p + 1, r}); } }

这段代码能跑，但栈的峰值深度在最坏情况下还是 O(n)。原因很朴素：先压左区间再压右区间，右区间会后处理；如果每次分区都极不平衡（比如左区间长 1、右区间长 n-2），那栈里会不断堆积左区间这种小碎片，同时右区间一直往下钻，栈深度跟着数据量线性增长。要压到 O(log n)，得让小的那个区间先出栈处理，大的后处理。

4.2 先压大区间、后压小区间，栈深度才是 O(log n)

栈是后进先出，所以"先出栈处理"意味着"后压栈"。要优先处理小区间，就得把小区间后压。

void quickSortIter(int a[], int n) { if (n <= 1) return; std::stack<std::pair<int,int>> st; st.push({0, n - 1}); while (!st.empty()) { auto range = st.top(); st.pop(); int l = range.first, r = range.second; if (l >= r) continue; int p = partitionHoare(a, l, r); int leftLen = p - l; int rightLen = r - p; if (leftLen < rightLen) { st.push({p + 1, r}); // 大区间先压，后处理 st.push({l, p - 1}); // 小区间后压，先处理 } else { st.push({l, p - 1}); st.push({p + 1, r}); } } }

这样做的效果是：任何时候栈里待处理的区间，长度都是从大到小排列的，而且每一层至少是上一层的两倍。既然区间长度最多翻 log n 次就到 n，栈里最多同时存在 log n 个区间，空间上界就是 O(log n)。这个推理和递归版"先递归小区间、尾递归大区间"是同一个道理，只是换了个存储介质。

手工走一遍小例子，数组[4, 2, 6, 1, 5]，n = 5。初始栈[(0,4)]。出栈(0,4)，假设分区后基准落在位置 2，左区间(0,1)长 1、右区间(3,4)长 1，两者一样长，走 else 分支：先压(0,1)再压(3,4)。栈变成[(0,1), (3,4)]。出栈(3,4)，长 1 的分区，再分完两个空区间，压进去再被跳过。再出栈(0,1)，同样处理完。栈清空，排序完成。整个过程栈的峰值就是 2，远小于 n。

4.3 只递归小区间、循环处理大区间

还有一种更省内存的写法：不用显式栈，只把"递归小区间"这一步留着，大区间用 while 循环接住，这就是编译器对尾递归的优化思路，手动做一遍。

void quickSortTail(int a[], int l, int r) { while (l < r) { int p = partitionHoare(a, l, r); if (p - l < r - p) { quickSortTail(a, l, p - 1); // 小区间递归 l = p + 1; // 大区间用循环接住 } else { quickSortTail(a, p + 1, r); r = p - 1; } } }

递归深度被限制在 log n 以内，栈帧总量极少，代码也比显式栈版本短。这个写法在 C++ 里很常用，因为编译器对 while 循环的处理比函数调用干净得多。两个版本我都实测过，在 100 万随机整数上耗时差异在 5% 以内，属于噪声范围，选哪个更多看团队代码风格。

注意：非递归版里if (l >= r) continue;这行千万别省。很多人写成if (l == r) continue;，单元素是跳过了，但分区在边界上会产生l > r的空区间（比如基准就在 l 位置，左区间是(l, l-1)），这种空区间送进分区函数，a[l]直接越界读到垃圾值，行为不可预测。

4.4 非递归真的"更快"吗

这里要说句公道话：非递归版在速度上通常不会更快，因为手动维护的std::stack操作本身就是函数调用，还有堆分配的开销，跟系统栈比起来并没有优势。非递归唯一的价值是内存可控——你能明确知道需要多少额外空间，能自己决定栈的数据结构（比如换成固定大小的数组，栈满时降级），能避免系统栈溢出导致的进程崩溃。在嵌入式、实时系统或者某些对栈大小有硬限制的运行环境里，这个价值是决定性的。

所以别被"非递归就是优化"这种说法带偏。如果只是普通业务代码，数组规模在百万以内，递归版加三数取中已经完全够用，递归深度撑死几十层。真要上非递归，动机应该是"我的栈空间紧张"，而不是"听说非递归更快"。

5. 三路划分与三路归并：重复元素和数据分块的两条路

标题里提到的"三路"其实指向两个不同的东西：一个是三路划分的快排，解决重复元素问题；另一个是三路归并排序，把序列切成三段分别排序再合并。方向不同，解决的问题也不同，我分开讲，最后给一个选型对照。

5.1 三路划分：一趟切成小于、等于、大于三块

朴素分区只分两块（不大于、不小于），等于基准的元素被随机甩到某一边，下次递归还得重新处理。如果数组里有大量重复值，比如 100 万个元素只有 3 种取值，那每一层分区都会把绝大多数元素分到同一侧，递归深度接近 n，直接 O(n^2)。

三路划分的思路是：既然等于基准的元素已经就位了，为什么还要递归处理它们？一趟分区直接切成< pivot、== pivot、> pivot三块，等于区不参与递归。

void quickSort3Way(int a[], int l, int r) { if (l >= r) return; int idx = l + rand() % (r - l + 1); // 随机化，避免有序数据退化 std::swap(a[l], a[idx]); int pivot = a[l]; int lt = l; // [l, lt) 区间内元素 < pivot int i = l; // [lt, i) 区间内元素 == pivot int gt = r; // (gt, r] 区间内元素 > pivot while (i <= gt) { if (a[i] < pivot) std::swap(a[lt++], a[i++]); else if (a[i] > pivot) std::swap(a[i], a[gt--]); else ++i; } quickSort3Way(a, l, lt - 1); quickSort3Way(a, gt + 1, r); }

三个指针的含义必须记牢：lt指向小于区的右边界（左闭右开），i是当前扫描位置，gt指向大于区的左边界（右开）。循环条件是i <= gt，因为i和gt相遇时gt位置上的元素还没被检查过。

手工走一遍最能看明白。数组[4, 2, 4, 1, 3]，l = 0, r = 4，假设随机化后还是取 a[0] = 4 作基准，lt = 0, i = 0, gt = 4。

第一步，i = 0，a[0] = 4 等于基准，走 else 分支，i 变 1。第二步，i = 1，a[1] = 2 小于基准，交换 a[0] 和 a[1]，数组变[2, 4, 4, 1, 3]，lt 变 1，i 变 2。第三步，i = 2，a[2] = 4 等于基准，i 变 3。第四步，i = 3，a[3] = 1 小于基准，交换 a[1] 和 a[3]，数组变[2, 1, 4, 4, 3]，lt 变 2，i 变 4。第五步，i = 4，a[4] = 3 小于基准，交换 a[2] 和 a[4]，数组变[2, 1, 3, 4, 4]，lt 变 3，i 变 5。此时 i > gt，循环结束。

最终 lt = 3、gt = 4，小于区是[0, 2]即[2, 1, 3]，等于区是[3, 4]即[4, 4]，大于区为空。递归处理(0, 2)和(5, 4)（后者为空直接返回）。结果正确，而且两个 4 一次都没参与后续递归。

这个算法在重复元素多的数据上的提速是数量级的。全相同的 100 万元素数组，朴素快排要递归到几十万层（虽然有随机化会好一些，但仍会产生大量无效的递归调用），三路划分只需要一趟扫描加一次递归判断，直接 O(n) 结束。

5.2 三路归并排序：把序列切成三段来合并

三路归并是归并排序的一个变体：普通归并把序列切成两段，三路归并切成三段，递归排好之后再做一次三路合并。

void merge3(int a[], int tmp[], int l, int m1, int m2, int r) { int i = l, j = m1 + 1, k = m2 + 1, t = l; while (i <= m1 && j <= m2 && k <= r) { if (a[i] <= a[j] && a[i] <= a[k]) tmp[t++] = a[i++]; else if (a[j] <= a[i] && a[j] <= a[k]) tmp[t++] = a[j++]; else tmp[t++] = a[k++]; } while (i <= m1 && j <= m2) tmp[t++] = (a[i] <= a[j]) ? a[i++] : a[j++]; while (j <= m2 && k <= r) tmp[t++] = (a[j] <= a[k]) ? a[j++] : a[k++]; while (i <= m1 && k <= r) tmp[t++] = (a[i] <= a[k]) ? a[i++] : a[k++]; while (i <= m1) tmp[t++] = a[i++]; while (j <= m2) tmp[t++] = a[j++]; while (k <= r) tmp[t++] = a[k++]; for (int x = l; x <= r; ++x) a[x] = tmp[x]; }

三段合并的全部复杂度在"取三个队头的最小值"这一步。注意判断用的是<=，相等时优先取靠前段的元素，这是保证稳定性的关键——相同值的元素，原本靠前的段先输出，相对次序不会被打乱。

但说实话，三路归并在内存里的表现通常不如二路归并。二路归并每层合并两个有序段，取最小值只需要一次比较；三路归并每层取最小值需要两次比较，层数从 log2 n 降到 log3 n，两者相乘之后总比较次数反而增加了大约 26%。再加上三路合并的代码分支更多，缓存局部性更差，实际跑起来大概是二路归并的 1.2 到 1.4 倍耗时。

那三路归并还有用吗？有，但不在内存排序里。它的价值体现在外部排序和多路归并场景：当数据量大到内存装不下，需要分批读盘、归并写盘时，归并的路数决定了读盘趟数。二路归并的趟数是 log2 n，三路就是 log3 n，m 路就是 logm n。减少一趟读写，省下的磁盘 IO 时间远超那点比较开销。这个道理和"内存里二路归并更快"并不矛盾，两者优化的是完全不同的资源。

5.3 三路快排和三路归并的选择边界

结论很明确：内存里排一份普通数据，重复值多就三路快排，要求稳定就归并；上不了内存，走多路归并。别为了"三路比二路听起来高级"就在内存排序里硬用三路归并，那是给自己添麻烦。

6. 常见问题与排查实录

这一节是我自己踩过和帮别人看过的问题里挑出来的高频项，按"现象—原因—怎么定位—怎么改"的顺序写，基本覆盖了这块内容 90% 的翻车场景。

6.1 分区函数写错的四种典型症状

症状一：程序卡死，没有任何输出。十有八九是内层 while 缺了i < j这个条件，指针在某一边一路走到越界，或者两边都不动形成死循环。定位方法很简单，在 while 循环里加一句打印 i、j 和数组内容，跑一个 5 元素的例子，看指针是不是在某一步不走了。修法是给每个内层 while 补上i < j的短路条件，注意顺序是while (i < j && a[j] >= pivot)，i < j必须写在前面，因为&&是短路求值，写后面等于没写。

症状二：小数据正确，20 个以上的随机数据出错。这是最阴险的一类，通常和"指针谁先走"或者基准位置有关。用[1, 5, 3]这种三元素数组测不出来，一上规模就露馅。定位方法是写一个对拍脚本：随机生成 1000 组长度 20 到 50 的数组，一组送快排，一组送std::sort，逐项比对。这个脚本我至今还留着，改一次分区函数就跑一遍，比肉眼审查可靠得多。

症状三：数组里有元素被"吃掉"或者重复。挖坑法最容易出这个问题，因为它是"覆盖写"而非"交换写"，中间态会出现重复值。如果最后的a[i] = pivot漏了，或者坑的位置算错了，就会出现某个元素丢失、另一个元素重复的情况。检查方法是排序完成后再扫一遍，用哈希表统计每个值的出现次数，跟原数组比对。

症状四：明明排完了，但顺序还是不对。大概率是递归区间写错，比如写成quickSort(a, l, p)而不是quickSort(a, l, p - 1)，把基准元素又送回左边，形成无限递归或者逻辑错乱。递归区间必须是[l, p-1]和[p+1, r]，因为 p 位置的元素已经在最终位置上了。

6.2 性能退化与栈溢出怎么定位

快排的所有性能问题最后都归结到一件事：分区不平衡。判断分区是否平衡，最直接的办法是统计递归深度。在递归函数入口加一个深度计数，每层加一，退出时减一，记录最大值。对 100 万元素，正常的最大深度应该在 20 到 40 之间（log2 100万约等于 20，加上常数波动）；如果看到最大深度是几千甚至上万，说明分区严重不平衡，基准选择有问题。

具体的退化成因有三种。数据已经有序或逆序，取端点作基准；数据里有大量重复值，严格不等号判断把相等元素全推到一边；数据本身分布极度倾斜，比如 99% 的元素集中在某个小范围。三种情况的修法分别是：三数取中或随机化、三路划分、随机化加三路划分。

栈溢出就更好定位了：进程直接退出，没有异常信息，或者调试器停在某个莫名其妙的地址。这时候看递归深度就知道是不是深度问题。100 万元素如果递归深度上千，那是必然爆的。改法是换非递归版，或者"小区间递归、大区间循环"的尾递归写法。

6.3 常见问题速查表

7. 实测数据与调参经验

聊性能不实测就是空谈，我在本机用 C++ 写了一套对拍加计时的程序，编译开 -O2，数据是随机生成的 int 数组，每组跑 5 次取中位数。下面的数字跟具体机器、编译器版本、数据分布强相关，看相对趋势就行，别把绝对值当结论。

从这张表里能读出几条很实在的结论。

第一，随机数据下三种递归写法几乎没差别。差异都在 10% 以内，属于实现细节和测量噪声的范围。别为了这 5% 的差异纠结用哪种，把正确性和随机化做好收益大得多。

第二，三路划分在随机数据上要慢 10% 左右。因为它多了两个指针的维护和分支判断。这个代价值得付，但要付在正确的地方——如果你的数据重复率很低，用三路纯属浪费；如果重复率高，普通二路快排会慢上百倍，三路只慢 10%，这笔账怎么算都划算。

第三，没做随机化的快排在有序数据上必然爆栈。这不是"可能"，是"一定"。递归版 100 万元素升序输入，跑到一半进程就没了。这个结论值得写进任何一份代码规范里。

第四，近乎有序的小数组上，快排完全不是最优解。10 万元素只有 100 处乱序，插入排序大概 1 ms 就搞定，快排要 7 ms。这就是为什么很多标准库的排序实现在数组长度小于某个阈值（常见是