分治排序实战：快速排序与归并排序的边界、优化与工程选型-育师

说实话，排序算法这关，我当年是在"能背代码但一改就错"的状态里卡了很久的。尤其是快速排序，网上一搜十种写法，有的递归区间是左闭右开，有的选最左做基准，有的搞三路快排，边界条件各说各话，背下来一套换一道题就废。最近帮一位刚入门的读者排查快速排序的代码，三个边界错误全是同一个根因，我又把这些老伙计从头撸了一遍。

这篇东西不打算做那种"是什么+代码+复杂度"的干巴巴教程。我直接用C++把这套分治排序从头实现了一遍，重点放在三件事上：分治思想为什么在排序这里体现得最透彻、快排和归并各自的边界到底怎么记、以及真实项目和算法题里什么时候必须用哪个。适合正在刷算法题的人，也适合准备面试手写排序的人，如果你只想把std::sort用明白，后面工程选型那一节也可以直接参考。

1. 分治思想的实战场：为什么排序是理解分治的最佳入口

1.1 分治不是"递归"的另一个名字

很多资料把分治和递归混着讲，实际上递归只是分治的一种实现手段，分治本身是"分解—解决—合并"三步走的思维框架。第一步，把一个规模为n的问题拆成若干规模更小的子问题；第二步，子问题小到可以直接求解时，就直接返回结果；第三步，把子问题的解按某种规则拼成原问题的解。

这个框架听起来抽象，放进排序里一下就具体了。快速排序和归并排序都是标准的分治三步，但它们对"分解"和"合并"的侧重完全不同，这正是理解两者差异的钥匙。快速排序的重心几乎全在"分解"这个环节，它通过一个分区操作，把数组切成"左边都小、右边都大"的两段，切到子数组只剩一个元素时，整个数组天然有序，合并环节几乎是空操作。归并排序则相反，它的"分解"就是无脑对半切，递归到底后真正干活的地方是"合并"——需要不停地两个有序区间合并成一个更大的有序区间。

我用一个不太严谨但很上口的类比来记：快排像打扫楼栋时只扫每层的核心走廊，走廊扫干净了，整栋楼自然整洁；归并像一层一层彻底清理，每两层之间再合并整理一次。快排的"扫走廊"动作在分解阶段完成，归并的"扫走廊"动作在合并阶段完成。理解了这句话，你就不会把两个排序的代码结构搞混了。

1.2 同一个分治，两种完全不同的"合"

既然都是分治，那快速排序和归并排序的分治策略差异到底体现哪些具体维度上？我习惯用一张表直接对照，这张表手写排序前在心里过一遍，写代码的时候思路会清晰很多：

维度	快速排序	归并排序
分的方式	按基准值切分，左半小于等于基准，右半大于等于基准	按下标对半切分，不关心元素大小
合的工作量	分区完成后数组局部有序，合并阶段几乎为零	合并两个有序子数组，这是核心工作量
稳定性	不稳定，相等元素的相对顺序可能改变	稳定，相等元素的相对顺序保持不变
额外空间	O(1)，原地交换	O(n)，需要临时数组承载合并结果
最坏时间复杂度	O(n^2)，基准选择不当时退化	O(n log n)，对半切分保证了深度严格log n
递归深度	平均O(log n)，最坏O(n)	恒为O(log n)

这张表里最值得玩味的是最后一行。归并排序的递归深度是稳定的O(log n)，因为它每次都对半切，不受数据分布影响；快排的递归深度却取决于基准能不能把数组大致均分，理想状态是O(log n)，如果每次基准都是最大或最小值，递归深度直接退化成O(n)。很多深刻的问题，比如递归栈溢出、最坏情况超时，都藏在这一行的差异里。

所以，学这两个排序时不要把它们当成两套孤立代码，它们本来就是同一个"分治"思想下两个极端：一个把工作提前到"分"，一个把工作量压到"合"。下面两节分别手写这两个排序，我会把边界问题拆到最细，确保你合上书也能自己推出来。

2. 快速排序手写实录：双指针分区模板与边界记法

2.1 先背下这个双指针分区模板

我先给出一个简洁、统一的版本。整个排序过程我统一使用闭区间[l, r]表示当前要处理的数组范围，这也是C++里vector下标最自然的表达方式，跟在纸上推演的例子完全一致，可以减少转换误差。

#include <vector> #include <algorithm> // 双指针分区：把 nums[l..r] 按基准值切分，返回基准最终位置 int partition(std::vector<int>& nums, int l, int r) { int pivot = nums[r]; // 选最右侧元素作为基准 int i = l, j = r; // 左指针、右指针 while (i < j) { // 左指针向右找第一个大于基准的元素 while (i < j && nums[i] <= pivot) ++i; // 右指针向左找第一个小于基准的元素 while (i < j && nums[j] >= pivot) --j; // 两者都找到了且 i 仍在 j 左侧，就交换 if (i < j) { std::swap(nums[i], nums[j]); } } // i 和 j 相遇的位置就是基准应该待的位置 std::swap(nums[i], nums[r]); return i; } void quickSort(std::vector<int>& nums, int l, int r) { if (l >= r) return; // 空区间或单元素区间，天然有序 int p = partition(nums, l, r); // 分区，p 是基准最终位置 quickSort(nums, l, p - 1); // 递归排左半部分 quickSort(nums, p + 1, r); // 递归排右半部分 }

我强烈建议你就用这一个版本作为主模板。它有几个好处：pivot选最右侧，逻辑上和"j从右边动"天然配合；最终基准的落点恰好就是返回值，递归区间不需要做额外换算；双指针同时扫描，相比单指针的Lomuto分区（就是那种用一个i标记小于区间的写法）交换次数更少，常数上也更优。

顺着代码走一遍"5, 2, 4, 6, 1, 3"这个例子，pivot选3。一开始i=0指向5，j=5指向3。内层第一个while发现5大于3，停住；第二个while发现3不小于3，也停住；i仍然小于j，交换，数组变成"3, 2, 4, 6, 1, 5"。接着i向右走到2，2小于等于3，继续走；走到4时停下；j向左走到1，小于3，停下；交换，数组变成"3, 2, 1, 6, 4, 5"。i继续向右走到6，停下；j向左走，走到1时已经i=j了，循环结束。把nums[i]（6）和基准nums[r]（5）交换，数组变成"3, 2, 1, 5, 4, 6"，返回i=3。至此，5左边的元素全部小于等于5，右边的元素全部大于等于5，一次分区结束。

2.2 三个最常见的边界错误：等于号、终止条件和递归区间

我在实际帮人看代码时，快排出错基本都集中在这三个位置，而且相互还会叠加，查错时特别迷惑。这里逐个拆开讲，每个错误我都给出了错误特征和修正思路。

第一个错误是外层循环写成while (i <= j)。写成小于等于后，i和j会交叉，i可能跑到j右边去。比如上面那个例子，最后i走到6的位置（下标3），j也走到下标3，如果条件允许i继续走，i会变成4，然后和nums[r]交换时，交换的就不是正确位置了。记住：双指针分区的核心前提是两者最终相遇，而不是交错，所以外层条件必须是i < j。

第二个错误是内层循环的等于号处理。很多人在找"大于基准"时写成nums[i] < pivot，找"小于基准"时写成nums[j] > pivot。这样等于基准的元素永远不停下来，如果数组中都是相等的数字，i会一路走到r，j也一路走到l，最后基准换过去，分区结果变成只消掉一个元素，快速排序退化到O(n^2)。正确的做法是：左边跳过小于等于基准的，右边跳过大于等于基准的，等于基准的停下来参与交换。这样才能把相等的元素分散到两侧，避免全相等数组引起的退化。

第三个错误是递归区间没有正确偏移。partition返回p之后，基准元素已经在正确位置上，不需要再参与排序，所以递归范围是[l, p-1]和[p+1, r]。如果写成[l, p]和[p, r]，p会在下一次递归中被重复处理，而且只要p等于l或r，递归区间没有真正缩小，就会无限递归直到栈溢出。

这三个错误有一个统一的验证方法：拿一个只有两个元素的用例，比如"2, 1"，在纸上走一遍你的代码。两个元素的用例能把所有边界暴露出来，因为它只有一次分区、一次交换、一次递归，任何细微错误都会在这里现形。我每次改完快排代码，第一件事就是拿两个元素的数组跑一遍。

2.3 退化陷阱：有序数组与随机化改造

固定选最右侧元素当基准，有一个很隐蔽的坑：如果输入数组本身已经有序，比如"1, 2, 3, 4, 5"，每次选出的基准恰好是当前区间的最大值，分区后数组只能拆出一个元素，递归深度变成O(n)，总复杂度退化成O(n^2)。这在刷题平台上是真实存在的血泪教训，我曾经在面试现场被面试官问"如果这个数组正好排好序了，你的算法还快吗"，当场惊出一身汗。

解决方案有两个层次。第一个层次是加随机化：在partition之前，随机选一个下标，把该位置的元素和nums[r]交换，再走固定分区逻辑。这样即使输入数据有序，每次基准的位置也是随机的，从概率上保证了分区大体均衡。

#include <random> void quickSortRandom(std::vector<int>& nums, int l, int r) { if (l >= r) return; // 随机选择一个下标，与最右侧交换后再分区 int idx = l + (std::rand() % (r - l + 1)); std::swap(nums[idx], nums[r]); int p = partition(nums, l, r); quickSortRandom(nums, l, p - 1); quickSortRandom(nums, p + 1, r); }

第二个层次是三数取中：比较nums[l]、nums[mid]、nums[r]三个位置，把大小居中的那个交换到最右侧当基准。这个策略虽然不如随机化通用，但对付"近似有序"数据特别有效，而且没有随机数生成的开销。工程上很多实现会结合两者，比如先做三数取中，遇到极端数据再退化为随机化。对于刷题来说，随机化版本就够用了，记得引入<random>或者直接用std::rand()时先播个种子，避免每次都得到相同的"随机"基准。

3. 归并排序手写实录：二路归并的稳定与额外空间

3.1 递归二路归并的最小实现

归并排序的代码框架比快排更规整，因为"分"完全机械，难点集中在"合"的细节。同样是闭区间[l, r]：

// 合并两个有序区间 nums[l..mid] 和 nums[mid+1..r] void merge(std::vector<int>& nums, int l, int mid, int r) { std::vector<int> tmp(r - l + 1); int i = l, j = mid + 1, k = 0; // 双指针扫描，把较小者依次放入临时数组 while (i <= mid && j <= r) { if (nums[i] <= nums[j]) tmp[k++] = nums[i++]; else tmp[k++] = nums[j++]; } // 左侧或右侧剩余元素直接接上 while (i <= mid) tmp[k++] = nums[i++]; while (j <= r) tmp[k++] = nums[j++]; // 写回原数组 for (int t = 0; t < k; ++t) nums[l + t] = tmp[t]; } void mergeSort(std::vector<int>& nums, int l, int r) { if (l >= r) return; int mid = l + (r - l) / 2; // 防溢出写法 mergeSort(nums, l, mid); // 递归排序左半 mergeSort(nums, mid + 1, r); // 递归排序右半 merge(nums, l, mid, r); // 合并两个有序区间 }

注意第9行的mid计算，我特意写成l + (r - l) / 2而不是(l + r) / 2。对int来说，当l和r都接近INT_MAX时，两者相加会溢出，产生未定义行为。刷题时数组长度一般不会触发，但工程代码里这是一个值得养成的习惯。中间点用这个写法，在很多二分、分治代码里都能复用，一次记住不亏。

合并过程可以拿"1, 4, 7"和"2, 5, 8"两组来模拟：左边指针指向1，右边指向2，1小，放入临时数组，左指针右移；然后4和2比，2小，放入临时数组，右指针右移；4和5比，4放入；7和5比，5放入；7和8比，7放入；左边剩8，右边也剩8，但左边第一个while已经结束了，右边第二个while把8放入。最终临时数组就是"1, 2, 4, 5, 7, 8"，全部写回原数组。整个流程没有任何跳步，非常机械，最好记。

3.2 合并过程为什么这么写

很多人背归并代码时，最难理解的是"为什么要开临时数组，不能直接在原数组上换吗"。答案是：合并两个相邻的有序区间，本质上是一个线性归并过程，必须有一个"中间存储"来暂存结果，否则在覆盖原数组时会把还没比较的元素冲掉。举个例子，nums[l..mid]是"1,4,7"，nums[mid+1..r]是"2,5,8"，如果直接把2写到nums[l]的位置，原来的1就被覆盖了，后面就没法继续比较了。

这个临时数组的空间复杂度是O(n)，不是O(n log n)。很多初学者误以为每个递归层都要开一份完整数组，实际上每层递归的merge只针对当前区间开对应大小的临时数组，这些数组随递归返回就释放了。虽然从"某一瞬间的峰值内存"看，递归栈上同时存在多个临时数组，但C++的vector在函数返回时会自动析构，峰值叠加起来仍然是O(n)级别的，通常可以放心使用。

归并排序的稳定性也体现在merge函数里的一个关键细节：当nums[i]等于nums[j]时，优先取左边元素，也就是if (nums[i] <= nums[j])而不是<。这样做保证相等元素的相对顺序在合并后保持一致。如果写成<，遇到相等元素时会先取右边元素，相等元素的前后关系就被反转了，稳定性就丢了。这是一道很经典的面试追问：归并排序为什么稳定？答案就在这个小于等于号上。

3.3 自底向上写法，以及空间问题的工程应对

递归版本的归并排序代码简洁，但递归调用本身有函数栈开销，而且在数据量极大时，可能会因为递归深度过大带来栈压力。这时候可以改用自底向上的迭代版本，核心思路是：先把数组看成n个长度为1的有序区间，然后两两合并成长度为2的有序区间，再合并成长度为4的区间，直到整个数组有序。

void mergeSortBU(std::vector<int>& nums) { int n = nums.size(); for (int width = 1; width < n; width <<= 1) { for (int l = 0; l < n; l += 2 * width) { int mid = std::min(l + width - 1, n - 1); int r = std::min(l + 2 * width - 1, n - 1); if (mid < r) { merge(nums, l, mid, r); } } } }

这里的width是当前有序区间的半长，内层循环每次处理长度为2*width的一段。最后一个区间的边界可能超数组长度，所以用min截断。mid < r的判断是防止最后一个区间只有一半长度、无需合并的情况。这段代码可以直接复用前面写好的merge函数，两者搭配起来非常顺手。

关于空间问题的工程应对，如果数据量特别大，可以一次性分配一个全局临时数组，然后每次merge时在同一个临时数组的不同区间段操作，避免频繁new、delete造成内存抖动。还有一种思路是"原地归并"，通过旋转数组的方式把两个有序区间原地合并，但实现复杂且常数极大，工程上很少用。做算法题时，递归版本的额外O(n)空间通常都能通过，不用过早优化。

4. 快排与归并的工程选型：实际项目里到底用哪个

4.1 稳定性：看起来很小，翻车却要命

很多刚工作的同学不太理解稳定性到底意味着什么，我讲一个真实场景：一个交易系统需要先按用户ID对交易记录排序，再按交易时间排序。如果第二次排序用的是快排，因为快排不稳定，相同时间戳的记录顺序会被打乱，用户ID的排序结果就白做了。这时候如果改用归并排序，由于稳定，第二次排序不会破坏第一次排序的相对顺序，用户ID的排序结果就保住了。

稳定性的本质是"排序过程是否会破坏相等元素原有的相对顺序"，在实际业务里，这直接关系到一个复合排序是否可靠。C++的std::sort不能保证稳定性，而std::stable_sort可以，前者的核心实现是快速排序的改良版（IntroSort），后者是归并排序。如果你在写业务代码时发现排序结果时对时错，先检查一下"我到底用的是sort还是stable_sort"，再检查一下"这次排序是否依赖了上一次排序的顺序"。

4.2 内存、递归深度与海量数据

快速排序是原地排序，额外空间复杂度O(1)，递归栈平均O(log n)，这是它最大的优势。归并排序需要O(n)的额外空间，在数据量很大时，这个额外空间会成为瓶颈。我见过一个处理上亿条日志的场景，用归并排序直接内存吃紧，最终换成了原地快排，内存瞬间降下来。但反过来，如果数据量大到连内存都放不下，那就得使用外部排序了，归并排序反而是更适合外部排序的框架，因为它每次只处理一部分数据，可以分段读入、分段合并。

从递归深度看，快排的最坏情况递归深度是O(n)，虽然随机化之后概率极低，但不是零。在递归调用栈较小的嵌入式环境里，一个极端输入就可能触发栈溢出。归并排序的递归深度严格是O(log n)，这点比快排更可控。所以在嵌入式、实时系统这类对确定性要求极高的场景，我倾向于选择归并排序或者直接用std::stable_sort。

4.3 STL的混合策略值得抄作业

C++标准库里对于排序实现的选择，其实是一份很优秀的工程答卷。std::sort并不是单纯快排，而是一个混合策略：在数据量小的时候切到插入排序，因为插入排序在小数组上的常数极小；递归深度超过某个阈值时，切到堆排序，保证最坏时间复杂度依然是O(n log n)。这个混合策略就是著名的Introsort。

我建议你抄这份作业，在实现自己的排序时，也可以参考这个思路：当区间长度小于16时，直接用插入排序收尾；快排递归前先比较区间大小，优先递归小区间。为什么优先递归小区间？因为可以控制递归栈深度，避免栈溢出，这个技巧在写其他分治算法时同样适用。

void quickSortOpt(std::vector<int>& nums, int l, int r) { while (l < r) { if (r - l < 16) { // 小区间使用插入排序，常数小 for (int i = l + 1; i <= r; ++i) { int key = nums[i], j = i - 1; while (j >= l && nums[j] > key) { nums[j + 1] = nums[j]; --j; } nums[j + 1] = key; } return; } int p = partition(nums, l, r); // 先递归小区间，再循环处理大区间，控制栈深度 if (p - l < r - p) { quickSortOpt(nums, l, p - 1); l = p + 1; } else { quickSortOpt(nums, p + 1, r); r = p - 1; } } }

这段优化逻辑在工程里很常见，面试时如果能把"为什么小区间用插入排序、为什么优先递归小区间"讲清楚，会是一个很好的加分项。实际项目中，非必要不用自己写排序，std::sort和std::stable_sort已经足够健壮，但理解它背后的设计逻辑，对你排查排序类问题会有很大帮助。

5. 刷题与面试中的高频变形：从排序到解决问题的思维迁移

5.1 归并排序求逆序对

归并排序最常见的一个变形题是"数组中的逆序对"，核心思路是在merge的过程中顺便统计：当右边区间的某个元素小于左边区间的某个元素时，左边区间中从这个元素开始到mid的所有元素，都能和它构成逆序对。

long long reversePairs(std::vector<int>& nums, int l, int r) { if (l >= r) return 0; int mid = l + (r - l) / 2; long long cnt = 0; cnt += reversePairs(nums, l, mid); cnt += reversePairs(nums, mid + 1, r); std::vector<int> tmp(r - l + 1); int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) { if (nums[i] <= nums[j]) { tmp[k++] = nums[i++]; } else { tmp[k++] = nums[j++]; cnt += mid - i + 1; // 关键：左区间剩余元素都比 nums[j] 大 } } while (i <= mid) tmp[k++] = nums[i++]; while (j <= r) tmp[k++] = nums[j++]; for (int t = 0; t < k; ++t) nums[l + t] = tmp[t]; return cnt; }

这个做法的正确性来源于一个事实：归并过程中，左区间和右区间都已经各自有序，当nums[j] < nums[i]时，左区间从i到mid的所有元素都大于nums[j]，这些就是右区间当前元素的全部逆序对数量。直接累加mid - i + 1就行。相比双重循环的O(n^2)，这个优化把复杂度降到O(n log n)，是归并排序"合并即统计"的经典应用。

5.2 快速选择解答TopK问题

快排的partition函数还有一个绝佳的应用，就是"数组中第k大的元素"或"最小的k个数"。思路是：partition返回基准的最终位置p，如果p正好等于目标位置k，那就直接得到答案；如果p大于k，说明答案在左半区间，只需递归处理左半；如果p小于k，说明答案在右半区间，递归处理右半。这样就省去了对另一半的排序工作，整体期望时间复杂度从O(n log n)降到O(n)。

int quickSelect(std::vector<int>& nums, int l, int r, int k) { if (l == r) return nums[l]; // 随机化基准，避免最坏情况 int idx = l + (std::rand() % (r - l + 1)); std::swap(nums[idx], nums[r]); int p = partition(nums, l, r); if (p == k) return nums[p]; return p < k ? quickSelect(nums, p + 1, r, k) : quickSelect(nums, l, p - 1, k); }

这里k表示在排序后数组中的下标位置。拿第k大的元素举例，如果数组下标从0开始，第k大的元素就是排序后下标n-k的位置。调用时传入k = n - k就能得到正确结果。快速选择是快排最实用的变体，很多TopK问题、中位数问题都能用这个模板直接解。

5.3 一套靠谱的排序验证与调试方法

手写排序最大的痛点是"看起来对但结果错"，我总结了一套验证流程，能帮你快速定位问题。第一步，写一个isSorted校验函数，每次排序完成后检查数组是否严格非降序：for (int i = 1; i < n; ++i) if (nums[i] < nums[i-1]) return false;。第二步，用三组数据测试：随机数组、大量重复元素的数组、已经有序的数组。随机数组测一般情况，重复数组测等于号处理，有序数组测退化问题。

第三步，当结果出错时，把数组规模缩小到10以内，并且在代码里打印每次分区的结果。比如快排的partition返回后，输出l、p、r以及当前数组，这样你能直观看到哪一步切分出了问题。第四步，使用断言代替手动检查，在调试版中启用assert(isSorted(nums))，如果中途断言失败，就能定位到具体是哪一次递归或合并出的问题。

还有一个非常实用的技巧：拿标准库排序当参照物。先拷贝一份原始数组，用std::sort排一遍，再把你自己的排序结果逐位对比。这个做法省去了肉眼检查的麻烦，尤其在刷题调试时特别高效。我自己排查归并排序的边界错误时，就是用这个方法快速定位到merge里某一处写回位置的下标偏移错了。