OI-wiki 归并排序全解析：稳定分治排序、合并过程与逆序对计数

OI-wiki 归并排序全解析稳定分治排序、合并过程与逆序对计数【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki归并排序Merge Sort是 OI / ICPC 中最重要的基于比较的稳定排序算法之一本文以 OI-wiki 的 merge-sort 章节 为主体系统讲解其定义、复杂度性质、合并merge核心过程、递归与倍增两种实现方式并深入其在 O(n log n) 时间内统计逆序对这一竞赛高频应用同时结合本仓库中的参考实现与分治专题进行源码级佐证。读完本文你将掌握可稳定复用的归并排序模板以及用归并过程顺带求解逆序数的完整方案。定义与基本性质定义归并排序merge sort是一种高效的、基于比较的稳定排序算法它能保证排序前后相等元素的相对次序不变这是它与快速排序、堆排序相比的重要优势也是它在很多要求「稳定」的题目中被优先选用的原因。时间复杂度与空间复杂度归并排序基于分治思想将数组分段排序后合并。其复杂度特征可以总结为时间复杂度最优、最坏与平均情况下均为 $\Theta(n \log n)$。无论输入数据如何分布归并排序总是严格地把问题对半拆分因此不存在快速排序那样「退化为 $O(n^2)$」的最坏情形空间复杂度$\Theta(n)$。归并排序需要与原数组等长的辅助数组来暂存合并结果这也是它相对原地排序算法如堆排序的主要代价。需要指出的是从理论上归并排序可以只使用 $\Theta(1)$ 的辅助空间即原地归并但实现复杂且常数较大。正如 OI-wiki 所述为便捷通常使用与原数组等长的辅助数组。在竞赛中使用辅助数组的 $O(n \log n)$ 时间 $O(n)$ 空间版本是标准做法也是后续所有参考实现的基础。与分治思想的关系归并排序是分治法的典型范例。在仓库的 divide-and-conquer.md 中归并排序被用来示例分治的套路分解 - 解决触底- 合并回溯。其递归结构形如二叉树的后序遍历先左右分解再处理合并回溯即退栈。仓库中以 C 和 Python 分别给出了递归与非递归两种merge_sort写法见 divide-and-conquer.md其中非递归版本正是下文将要讲解的「倍增法」。核心过程合并Merge归并排序最核心的部分是合并merge过程将两个有序数组a[i]和b[j]合并为一个有序数组c[k]。合并算法描述从左往右枚举a[i]和b[j]找出当前两个数组首元素中的最小值放入c[k]重复上述过程直到a和b中有一个数组为空将另一个数组剩下的元素依次放入c[k]。稳定性的关键比较符号的选择合并过程的比较符号直接决定排序的稳定性当前段首元素小于或等于后段首元素a[i] b[j]时而非小于时a[i] b[j]就要把前段元素作为最小值放入c[k]。用代码语言表达就是先判断后段是否严格小于前段b[j] a[i]只有后段严格更小才取后段否则取前段。这样相等元素永远是「前段的先被取走」从而保证相等元素的原始相对次序在合并后不被破坏。实现一数组下标实现C/Cvoid merge(const int *a, size_t aLen, const int *b, size_t bLen, int *c) { size_t i 0, j 0, k 0; while (i aLen j bLen) { if (b[j] a[i]) { // ! 先判断 b[j] a[i]保证稳定性 c[k] b[j]; j; } else { c[k] a[i]; i; } k; } // 此时一个数组已空另一个数组非空将非空的数组并入 c 中 for (; i aLen; i, k) c[k] a[i]; for (; j bLen; j, k) c[k] b[j]; }实现二指针实现C/Cvoid merge(const int *aBegin, const int *aEnd, const int *bBegin, const int *bEnd, int *c) { while (aBegin ! aEnd bBegin ! bEnd) { if (*bBegin *aBegin) { *c *bBegin; bBegin; } else { *c *aBegin; aBegin; } c; } for (; aBegin ! aEnd; aBegin, c) *c *aBegin; for (; bBegin ! bEnd; bBegin, c) *c *bBegin; }指针版本用「半开区间」[begin, end)描述两个待合并的有序段语义更贴近 C 迭代器风格也便于直接用于递归与倍增实现。实现三使用标准库 mergeC 的algorithm库提供了现成的merge函数用法与上述指针式写法相同传入两段半开区间与输出位置可直接替代手写合并减少出错概率#include algorithm // merge(first1, last1, first2, last2, d_first); std::merge(a l, a mid, a mid, a r, tmp l);实现四Python 实现def merge(a, b): i, j 0, 0 c [] while i len(a) and j len(b): # ! 先判断 b[j] a[i]保证稳定性 if b[j] a[i]: c.append(b[j]) j 1 else: c.append(a[i]) i 1 # 此时一个数组已空另一个数组非空将非空的数组并入 c 中 c.extend(a[i:]) c.extend(b[j:]) return cPython 版本利用切片a[i:]、b[j:]直接追加剩余元素代码更简洁注意稳定性判断与 C/C 版本完全一致。分治法递归实现归并排序算法流程边界条件当数组长度为 $1$ 时该数组已经是有序的不需要再分解递归分解当数组长度大于 $1$ 时将该数组分为两段分别对两段递归排序合并将两个有序子段合并为一个有序数组。用数学归纳法可以证明该流程能够将任意数组转变为有序数组。为了保证 $O(n \log n)$ 的复杂度通常将数组分为尽量等长的两段即取$$ mid \left\lfloor \dfrac{l r}{2} \right\rfloor. $$实现C/C注意下面的代码所表示的区间分别是 $[l, r)$、$[l, mid)$、$[mid, r)$void merge_sort(int *a, int l, int r) { if (r - l 1) return; // 分解 int mid l ((r - l) 1); merge_sort(a, l, mid), merge_sort(a, mid, r); // 合并 int tmp[1024] {}; // 请结合实际情况设置 tmp 数组的长度与 a 相同或使用 // vector先将合并的结果放在 tmp 里再返回到数组 a merge(a l, a mid, a mid, a r, tmp l); // pointer-style merge for (int i l; i r; i) a[i] tmp[i]; }几点实用提示区间约定全程采用左闭右开区间 $[l, r)$mid l ((r - l) 1)在求中点时避免了(l r)可能产生的整数溢出是竞赛中的推荐写法临时数组示例中的tmp[1024]仅为示意实际使用时应将tmp的长度设置为与a相同或直接使用std::vectorint tmp(n)动态分配拷贝回写合并结果先写入tmp再统一拷回a[l..r)避免合并过程中覆盖尚未读取的原元素。实现Pythondef merge_sort(a, ll, rr): if rr - ll 1: return # 分解 mid (rr ll) // 2 merge_sort(a, ll, mid) merge_sort(a, mid, rr) # 合并 a[ll:rr] merge(a[ll:mid], a[mid:rr])Python 利用切片赋值直接完成「合并后回写」两步与 C 版本逻辑一一对应。倍增法自底向上、迭代实现归并排序递归实现需要调用栈的辅助空间且对栈深度敏感倍增法则完全不使用递归自底向上逐层合并是归并排序的迭代实现。算法流程初始状态已知长度为 $1$ 的数组是有序的将整个数组视作若干长度为 $1$ 的有序段逐层倍增从左往右依次合并两个长度为 $1$ 的有序段得到一系列长度 $\le 2$ 的有序段再从左往右依次合并两个长度 $\le 2$ 的有序段得到一系列长度 $\le 4$ 的有序段重复上述过程段长 $1 \to 2 \to 4 \to \cdots$直至数组只剩一个有序段。关于「$\le n$ 而不是 $ n$」数组的长度很可能不是 $2^x$此时在最后几轮就可能出现长度不完整的段甚至出现最后一个段独立存在、没有配对对象的情况。因此每一轮合并出的段长度是「不超过 $2^k$」而非严格等于 $2^k$。实现C/Cvoid merge_sort(int *a, size_t n) { int tmp[1024] {}; // 请结合实际情况设置 tmp 数组的长度与 a 相同或使用 // vector先将合并的结果放在 tmp 里再返回到数组 a for (size_t seg 1; seg n; seg 1) { for (size_t left1 0; left1 n - seg; left1 seg seg) { // n - seg: 如果最后只有一个段就不用合并 size_t right1 left1 seg; size_t left2 right1; size_t right2 std::min(left2 seg, n); // ! 注意最后一个段的边界 merge(a left1, a right1, a left2, a right2, tmp left1); // pointer-style merge for (size_t i left1; i right2; i) a[i] tmp[i]; } } }实现要点外层循环seg表示当前段长每轮翻倍seg 1内层循环每次取出两个相邻段 $[left1, right1)$ 与 $[left2, right2)$ 进行合并边界处理left1 n - seg保证「最后若只剩下一个独立段则无需合并」right2 std::min(left2 seg, n)防止第二段越界这是迭代写法中最容易出错的地方合并结果同样先写入tmp再回拷到a。实现Pythondef merge_sort(a): seg 1 while seg len(a): for l1 in range(0, len(a) - seg, seg seg): r1 l1 seg l2 r1 r2 l2 seg a[l1:r2] merge(a[l1:r1], a[l2:r2]) seg 1与 C 版本等价只是循环用range表达、合并用切片赋值完成。仓库 divide-and-conquer.md 中的非递归merge_sort使用std::merge/ Pythonmerge也采用了同样的「段长倍增」思路可作为对照阅读。进阶应用用归并排序统计逆序对逆序对的定义逆序对是满足 $i j$ 且 $a_i a_j$ 的有序数对 $(i, j)$。排序后的数组无逆序对一个排列中逆序对的总数称为该排列的逆序数。逆序数问题在排列组合、概率论与各类计数题中频繁出现相关理论背景见仓库的 permutation.md 逆序数章节。原理合并过程天然携带逆序信息归并排序的合并操作中每次后段首元素被作为当前最小值取出时说明它小于前段所有剩余元素——这些「前段剩余元素」的数量之和正是合并操作减少的逆序对数量。具体地当nums[j] nums[i]后段元素更小时前段区间[i, m)中所有元素都大于nums[j]因此本次合并贡献m - i个逆序对归并排序的分治结构保证每个数对恰好被统计一次因此可以在排序的同时求出全部逆序对数时间复杂度仍为 $\Theta(n \log n)$。仓库参考实现仓库在 docs/math/code/permutation/inversion_2.cpp 中提供了完整的「归并排序求逆序数」参考实现其关键代码为while (i m j e) { if (nums[j] nums[i]) { tmp[k] nums[j]; // In this case, all elements in [i,m) are larger than element j. res m - i; } else { tmp[k] nums[i]; } k; }注意两点计数发生在「后段元素被取出」分支中累加量为m - i前段剩余元素个数逆序对数量可能超过int范围如完全逆序排列参考实现使用long long存储结果实际题目中应同样注意数据范围。该实现位于 permutation.md 的参考实现折叠块中对应输入为n和长度为n的序列输出逆序数。其他解法逆序对计数还可以通过树状数组或线段树解决时间复杂度同为 $O(n \log n)$按值域建树从左到右扫描每扫到一个元素先查询「比它大的已出现元素个数」再将其加入树状数组。算法详细解释参见仓库的 fenwick.md 全局逆序对全局二维偏序章节其参考实现同样收录在 permutation.md 中inversion_1.cpp树状数组版本。归并排序方案与数据结构方案各有取舍前者实现直观、常数小且无需离散化后者在「二维偏序」类扩展问题上更通用。在 OI-wiki 中的延伸阅读归并排序并非孤立知识点它在本仓库多个专题中承担了承上启下的角色分治专题divide-and-conquer.md 以归并排序为第一个示例讲解分治的「分解 - 解决 - 合并」套路并给出递归/非递归两种写法与「merge_sort类似二叉树后序遍历」的直觉排列与逆序数permutation.md 逆序数 给出了逆序数的严格定义与置换奇偶性的联系以及归并排序、树状数组两种参考实现树状数组fenwick.md 全局逆序对 从数据结构角度再次解决逆序对问题可与此处归并排序解法对照学习排序总览sort-intro.md 对各类排序算法的适用场景做了横向比较可用于判断何时选用归并排序其他排序专题归并排序的「段合并」思想还延伸出 tim-sort.md 等混合排序算法可作进阶阅读。掌握了本文的合并写法、递归/倍增两种框架与逆序对计数技巧你便拥有了应对「稳定排序」「区间有序合并」「二维偏序计数」等一类题目的通用工具箱。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考