企业官网建设流程全解析

1. 从一道力扣题说起：归并排序为什么值得专门刷一遍

我习惯给每个熟悉的算法分类贴一个“使用场景”的标签：二分法对应有界单调，动态规划对应重叠子问题，而归并排序在我这儿标签是“跨越分割点做统计”。这个标签不是我一开始就明白的，是在刷了不少力扣题之后才慢慢体会到的。标题里写着“归并排序力扣题（leetcode）萍”，我猜这里的“萍”多半是“评测”的错别字。所以这篇文章就当作一次面向归并排序类刷题经验的复盘，把这类题从模板代码、题型变种到常见坑位一次说清楚。

先说结论：归并排序在力扣题里的价值，早就不是“把数组排个序”这么简单。很多一看就会让人犹豫的题，比如求逆序对数量、求某个带条件的配对数量、给链表排序，底层最稳妥的思路反而是归并排序。原因很简单，归并排序天然会把数组切分成左右两个有序区间，而在合并这两个区间的时候，左右指针天然能回答“左边有哪些元素相对右边满足某个大小关系”的问题。这个特性是快速排序、堆排序都给不了你的。

适合读这篇内容的人有这么几类。第一类是正在刷分治专题的新手，需要一个能反复复用的归并模板；第二类是面试前想集中突破数组、链表排序相关力扣题的老手；第三类更具体，是遇到一道题能想到“该用归并”，但写代码时总是在索引边界、辅助数组、递归出口这些地方卡住的同学。

这篇文章不会带你一个题号一个题号地过。因为这样容易被题目表象带偏，最后变成背代码。我希望把归并排序题拆成原理、模板、题型、排错四个层面，你拿着这套东西再去碰题，思路会顺很多。

2. 归并排序的底层逻辑与可直接套用的模板

先别急着写代码。刷题之前必须想清楚归并排序为什么长这个样子。很多人背得住代码，却答不上来“为什么合并过程能做到 O(n)”，一遇到变种题就懵。

2.1 三个关键操作：分、治、合

归并排序整个过程可以压缩成三个短语：分到不能再分，处理最小问题，再逐层合并。

• 分：把数组从中间切开，得到左半部分和右半部分。这一步对应递归调用里的分解逻辑。
• 治：最小的问题就是只有一个元素或者空数组，天然有序，不需要处理。递归会自动帮我们把半区排好序。
• 合：把两个已经有序的子数组合并成一个更大的有序数组。这一步是整个算法真正发生“比较”的地方，也是绝大多数力扣变种题做附加逻辑的地方。

让我用一个生活场景类比。你有两堆已经按身高排好的学生队伍，现在要把两队合并成一队，并且保持身高有序。最聪明的做法不是把所有人倒在一起重新排，而是让两个队伍各出一个代表，比较身高，矮的进新队伍，然后他后面的同学补上来，继续比。这样每一轮只比较队头两个人，不会回头重新比较已经站在新队伍里的人。这就是合并过程能做到 O(n) 的原因。

这种“两个有序序列只用比较队头就能合并”的性质，在算法题里会反复出现。你不需要真的维护一棵平衡树，也不需要做前缀离散化，只要在合并两个有序区间时，额外回答一个“跨区间满足某条件有几对”的问题就够了。

2.2 一个可以直接套用的归并模板

下面这份代码是排序数组这种纯排序题的标准写法。我推荐优先掌握基于索引和辅助数组的版本，而不是基于 Python 切片的版本。因为切片会高频申请新数组，实际评测时的内存和时间都不理想。面试手写也建议从索引版出发。

class MergeSort: def sortArray(self, nums): self.tmp = [0] * len(nums) self.merge_sort(nums, 0, len(nums) - 1) return nums def merge_sort(self, nums, l, r): if l >= r: return mid = (l + r) // 2 self.merge_sort(nums, l, mid) self.merge_sort(nums, mid + 1, r) self.merge(nums, l, mid, r) def merge(self, nums, l, mid, r): self.tmp[l:r + 1] = nums[l:r + 1] i = l j = mid + 1 k = l while i <= mid and j <= r: if self.tmp[i] <= self.tmp[j]: nums[k] = self.tmp[i] i += 1 else: nums[k] = self.tmp[j] j += 1 k += 1 while i <= mid: nums[k] = self.tmp[i] i += 1 k += 1 while j <= r: nums[k] = self.tmp[j] j += 1 k += 1

写这份代码时有几个细节需要额外注意。

第一，tmp数组的长度是len(nums)，每次合并前要把nums[l:r+1]的内容复制过去。原因是我们需要保留“合并前”的左右区间顺序，否则合并过程中直接覆盖nums会破坏还没处理的元素。

第二，比较时用<=还是<会影响排序的稳定性。用<=表示左区间元素不晚于右区间元素排列，这样相等的元素能保持原有相对顺序，这也是归并排序稳定性的来源。在一些要求“稳定排序”的面试题追问里，你说清楚这一点会很加分。

第三，三个 while 缺一不可。第一个 while 负责两边都有剩余元素时的正常比较，后两个分别负责左边或右边还有剩余时直接把尾巴拷回去。很多人写完第一个 while 就结束了，结果数组末尾总是丢元素。

2.3 时间复杂度与空间复杂度到底怎么算

归并排序的递归结构是一个满二叉树。每一层都要对 n 个元素做一次合并，每一层的合并总消耗是 O(n)，而递归深度是 log_2 n 层，所以总时间复杂度严格是 O(n log n)，不会因为输入的状态变好或变差而改变。

这一点和快速排序不一样。快速排序的平均时间是 O(n log n)，但遇上极端有序的输入，如果基准点选得不好，会退化到 O(n^2)。归并排序没有这个问题，它的切分点永远是中点，所以复杂度稳定。

空间复杂度方面，这份代码用了一个长度为 n 的辅助数组，递归栈深度是 O(log n)，所以总空间是 O(n)。有人会追问为什么不是 O(n log n)，关键在于递归栈在同一时刻最多只有一条从根到底的路径活跃，每一层的辅助数组都是同一块内存的不同区间视角，并不是每层都新开一份。

3. 力扣上归并排序题的四种常见考法

数组排序这种题目本身已经很多年不直接作为重点了，因为各大语言内置的排序足够快。真正有区分度的题，是那些表面上在考“计数”“链表”“数据流”的题，实际上核心解法还是归并。

3.1 第一种考法：纯排序题，重点在边界条件

这一类题目难度不高，但非常考验基本功。给你一个乱序数组，要求你手写排序完成升序排列。用上面的模板可以直接过。

纯排序题真正的失分点通常在三个地方：数组为空时递退出错、mid被固定写死导致右区间为空、合并后忘记把结果写回原数组。不要小看这些问题，评测平台一跑，往往就是 Runtime Error 或者 Wrong Answer。这一类题的作用更多是让你把模板刻进肌肉记忆，后面套变种题时不需要再花时间回忆每一行代码是干什么的。

3.2 第二种考法：在合并阶段做计数，典型如逆序对统计

这是归并排序在力扣题里最经典、最值得反复品味的一种形态。问题描述通常是：给定一个数组，如果i < j且nums[i] > nums[j]，那么(i, j)叫做一个逆序对，要求统计总数。

如果不假思索用双重循环，很快就能写出来，但 O(n^2) 在大数据量下直接超时。归并排序解法巧妙在哪里？它在合并左右两个有序区间的时候，如果发现右区间当前元素tmp[j]比左区间当前元素tmp[i]小，那么左区间从i到mid的所有元素，都因为已经有序而必然大于tmp[j]。这意味着这一轮可以一次性统计出mid - i + 1个逆序对，而不需要逐个元素再比较一遍。

这背后的直觉值得展开。当左区间是[2, 5, 7]，右区间是[1, 3, 6]时，合并到右区间元素1出场时，左区间的2, 5, 7都还在等待区，它们都比1大，所以产生了 3 个逆序对。之后右区间元素3出场时，左区间指针已经走到5，于是5, 7都比3大，又产生 2 个逆序对。整个过程不是“一个萝卜一个坑”地数，而是“指针滑过一段有序区间，直接按长度计数”，因此每个元素最多被指针经过常数次，总复杂度保持 O(n log n)。

3.3 第三种考法：链表排序，归并是天然解

数组有随机访问能力，所以稍微复杂一点的算法都能直接用下标。链表不行，它只能顺序访问。这时候快排在数组上的“左右指针法”搬到链表上就非常别扭，而堆排序也不适合直接操作链表。

归并排序只需要做两件事：切开链表，按顺序合并。这两个操作都可以只靠指针完成。

• 找中点：用快慢指针。快指针一次走两步，慢指针一次走一步，快指针到末尾时慢指针正好在中点。
• 合并两个有序链表：这是一个单独的反贪心式题目，把两个链表按值从小到大接起来。
• 递归出口：链表为空或只有一个节点时直接返回。

这里需要特别注意的是“断链”。递归处理右半部分之前，必须先让左半部分的末尾变成None，否则递归会把整条链表当成一个整体处理，导致死循环或元素重复。很多人在链表排序题上报错，不是归并逻辑不对，而是忘记在上一个节点处切断。

为什么链表排序用归并这么合适，还有一个深层原因：合并两个有序链表的过程只需要改变节点的next指针，不需要申请额外存储空间。相比数组归并需要的 O(n) 辅助空间，链表归并的空间复杂度可以做到 O(log n)，这部分空间来自递归栈。

3.4 第四种考法：归并思想变形，多路归并与外部排序

如果面试官想延伸，往往会问“如果内存装不下所有数据，怎么排序”。标准回答就是外部排序：把大文件切分成多个有序的小块，每个小块内部可以排序，然后做多路归并，用小顶堆维护多个有序段的头元素，每次弹出最小的那个，再从对应段补上。

力扣上也有类似思路的题目，比如把若干个有序数组合并成一个有序数组，或者给 K 个有序链表排序。这类题既可以写 K 个指针每次找最小值，也就是多路归并的直观理解，也可以用优先队列优化成 O(n log K)。归并排序在这里不再只是一种“数组排序算法”，而是一种“从多段有序数据中不断挑取最小值”的框架。

我建议刷题时把这类题也归类到归并的头下，而不是简单归类到“优先队列”标签底下。因为这样你才能明白优先队列只是实现手段，真正的决策逻辑是归并思想。

4. 核心实操：如何把模板改造成能过评测的题解

理解题型只是第一步。下面我以一个常见的变种问题为例，完整演示从模板到题解的过程。

假设现在有一道题：给定一个整数数组，统计满足i < j且nums[i] > 2 * nums[j]的下标对数量。这是一个比普通逆序对更苛刻的条件，因为右侧元素必须“大幅小于”左侧元素，才会计数。

这种题如果继续套双层循环，复杂度肯定是 O(n^2)。用归并排序做，核心变化只是在合并阶段增加一段“跨区间计数逻辑”。

4.1 第一步：先把纯排序模板跑通

我不建议一上来就写计数逻辑。先把上一章那个sortArray模板默写出来，确保能在评测系统里通过最简单的排序测试。这一步的意义是让辅助数组、索引和递归出口都进入稳定状态。模板不稳定，后面加任何逻辑都会让你怀疑是附加逻辑写错了，还是排序本身写错了。

4.2 第二步：在合并过程中加入跨区间计数

普通逆序对计数可以在合并的else分支顺便完成，因为只要右区间元素被选中，说明左区间当前及剩余元素都更大。

但是对于nums[i] > 2 * nums[j]这个条件，不能等到“右区间元素被选出”再做，因为右侧元素可能已经入库，左侧还有更大的元素。所以常见的稳妥写法是在真正的合并之前，先做一趟遍历专门计数。

i = l j = mid + 1 # 统计满足 nums[i] > 2 * nums[j] 的跨区间对数 while i <= mid: while j <= r and nums[i] > 2 * nums[j]: j += 1 count += j - (mid + 1) i += 1

这段逻辑里的j不需要在每次i变化后重置。原因在于左区间已经有序，i每次增加后，nums[i]只会变大，所以满足条件的右区间元素窗口只会向前移动，不会后退。如果每次重置j，复杂度就退化成了 O(n^2)。这是一个很典型的“双指针单调移动”场景。

4.3 第三步：完成合并，恢复有序性

计数完成后，数组还不能乱，因为后续递归层需要两个有序子区间继续向上合并。所以接下来正常执行merge过程。两部分逻辑互不影响，先计数后合并，符合“在合并阶段做文章”的套路。

这套顺序也方便面试讲解。你可以在纸上画两个有序数组，先给面试官讲计数双指针为什么单调不减，再讲合并过程怎么把两个数组变成有序大数组。逻辑层次清楚，不容易被追问卡住。

4.4 完整代码示例与逐步注释

class Solution: def reversePairs(self, nums): self.count = 0 self.tmp = [0] * len(nums) self.merge_sort(nums, 0, len(nums) - 1) return self.count def merge_sort(self, nums, l, r): if l >= r: return mid = (l + r) // 2 self.merge_sort(nums, l, mid) self.merge_sort(nums, mid + 1, r) self.merge(nums, l, mid, r) def merge(self, nums, l, mid, r): # 第一步：统计跨区间满足条件的对数 i = l j = mid + 1 while i <= mid: while j <= r and nums[i] > 2 * nums[j]: j += 1 self.count += j - (mid + 1) i += 1 # 第二步：正常合并，恢复原数组的有序性 self.tmp[l:r + 1] = nums[l:r + 1] i = l j = mid + 1 k = l while i <= mid and j <= r: if self.tmp[i] <= self.tmp[j]: nums[k] = self.tmp[i] i += 1 else: nums[k] = self.tmp[j] j += 1 k += 1 while i <= mid: nums[k] = self.tmp[i] i += 1 k += 1 while j <= r: nums[k] = self.tmp[j] j += 1 k += 1

分析一下这个写的复杂度和原版排序相同：每一层合并要多做一遍遍历来计数，但每层总长度仍为 n，所以整体仍是 O(n log n)。空间方面只多了一个计数变量，没有额外大块空间，所以空间复杂度仍为 O(n)。

5. 刷题时最常踩的坑与排查方法

不管模板背得多熟，一上评测多少都会碰到一些反常识的错误。我把这段时间整理出的高频问题列在下面，每一条都是我实际踩过或帮别人排查过的。

5.1 辅助数组复制错误

一个常见错误是复制辅助数组时写成了self.tmp = nums[:]，或者复制范围写错。如果只复制当前区间，应该用self.tmp[l:r+1] = nums[l:r+1]。如果全局复制为整段nums，后面指针在局部区间移动时，复制到tmp的内容会混入其它区间的旧数据，导致合并结果错乱。

另一个错误方向是合并完成后没有把tmp的结果写回nums，只更新了tmp。这会让递归回到上一层时看到的nums仍然是乱序的，计数自然也错。

5.2 递归边界和索引死循环

递归入口通常写成：

if l >= r: return

有些同学写成if l == r: return。单独看没问题，但一旦遇到空区间，也就是l > r的情况，就会继续递归，直到栈溢出。有些题目的区间控制变量比较复杂，比如按某个索引变形后调用，空区间不一定不会出现，稳妥起见写>=更保险。

mid也可能出问题。有人写mid = (l + r) // 2后，右递归写成了merge_sort(nums, mid, r)，于是区间重复包含mid，递归永远无法终止。正确的分区是左闭右闭情况下，左半变[l, mid]，右半变[mid + 1, r]。

5.3 计数双指针推进错乱

这一块错误通常出现在带附加条件的计数题里。

一种错误是外层i增加后，内层j重新回到mid + 1。这样虽然逻辑正确，但复杂度变成 O(n^2)，大数据量会直接超时，且难以通过评测。

另一种错误是在计数时修改了真正用于合并的指针位置。计数循环和合并循环如果共用变量，要先想清楚指针归位。我的建议是让两个循环用独立变量，计数用i, j，合并用p, q或者重新赋值，避免互相污染。

5.4 递归深度过大

数组长度达到十万甚至百万级别时，递归深度只有 log_2 n 左右，大概 17 层到 20 层，不会触发 Python 默认递归上限。但如果你在递归里用了切片或没有正确收敛边界，递归次数会异常膨胀，最终报 RecursionError。

如果真要保险，可以在代码开头加两行：

import sys sys.setrecursionlimit(10**6)

不过要明白这只是兜底，不能掩盖边界没写对的事实。

5.5 常见问题速查表

6. 我的实战体会和后续扩展方向

我发现很多人在做归并排序相关力扣题时，最大的问题不是不懂归并，而是没有形成“跨区间的相对比较”意识。如果你看到一道题，要求满足i < j同时nums[i]和nums[j]还满足某种具体条件，你第一反应可以从暴力法开始，但一定要在第二反应里想到归并。因为归并的合并过程，天然会把两个区间的相对顺序暴露在指针面前。

具体到我自己，现在拿到这类题会先在纸上画三步。第一步，把数组从中间切开后，左半边内和右半边内的答案交给递归处理；第二步，只看“左半边元素和右半边元素之间的配对”，这部分就是合并阶段能做的事；第三步，判断这种配对条件能不能通过双指针一次性统计。如果能，那十有八九是归并排序能解的题。

归并排序还有一个方向容易被忽略，就是自底向上的非递归版本。它与递归版本的区别在于不再用函数递归切分区间，而是先按长度为 1、2、4、8 的块逐步合并。好处是避免递归栈空间，在受限环境中更可控。代码上需要多写一层循环控制段长，并处理末尾不够一整段的情况。我建议递归版本写熟之后，再花半天时间把非递归版本写一遍，这样你会更清楚“合并”这一步其实与“划分”是怎么解耦的。

后续如果想继续深入，还可以研究下面几个扩展点。第一是计算逆序数类问题与树状数组方案的对比，归并排序适合在区间内自然递归，树状数组适合在线更新场景。第二是归并排序在“多路归并”题目中的应用，比如处理大量有序文件或链表，小顶堆是核心优化。第三是把归并思想用在“求区间和的个数”这类前缀和题目中，原理同样是“两个有序区间内满足相对条件”，只不过排序对象从原数组变成了前缀和数组。

最后分享一个小技巧。我刷归并排序变种题时，不会直接去网上搜“归并排序 力扣题 汇总”，而是先把自己写的模板存在代码片段里，每次遇到可疑题都要把模板抄一遍，再往里加附加逻辑。这样不仅提升了手感，也让我在面试现场手写这类题时不需要思考，完全变成肌肉记忆。归并排序表面看是排序算法，实际上是分治思想的一个高质量载体，真正吃透它之后，你再去看其他分治类题目，会发现思路开阔很多。