上一篇的二分查找要求数组有序。现在给出 [5, 2, 4, 1, 3],怎样把它整理成 [1, 2, 3, 4, 5]?
一种直接办法是反复寻找剩余元素中的最小值。它容易理解,但需要进行大约 n(n - 1) / 2 次比较。另一种思路是:把数组分成两半,分别排好序,再把两个有序部分合起来。
这里会遇到一个自然的问题:“给一半排序”仍然是排序,能不能继续使用同一种办法?这就把我们带到了递归与归并排序。
本文使用 Java 17+。系列目录 · 上一篇:二分查找与边界 · 下一篇:栈、队列与树
一、递归怎样停下来
递归是函数在执行过程中再次调用自身。它适合表达“解决较小的同类问题,再利用结果完成当前问题”的过程。
要写出能结束的递归,先回答两个问题:什么情况可以直接得到答案;下一次调用如何更接近这个情况。
排序的最小情况很简单:空数组和只有一个元素的数组已经有序。规模至少为 2 时,才需要拆成两个更短的部分。
因此,我们的递归函数接收一个半开区间 [left, right),长度为 right - left:
长度为 0 或 1 → 直接返回长度至少为 2 → 排左半段 → 排右半段 → 合并两个有序段每次拆分后,两边长度都小于原长度,沿着任意一条调用路径最终都会到达 0 或 1。缺少终止条件,或者下一次仍然传入相同区间,就会导致递归不断深入。
二、函数调用栈保存了什么
可以把调用栈理解为一叠“尚未做完的工作记录”。函数调用另一个函数时,当前执行位置和局部状态需要保留,等被调用的函数返回后继续执行。
即使调用的是自身,不同调用也有各自的参数和局部变量。外层的 left = 0, right = 5,不会因为内层收到了 left = 0, right = 2 就被改成后者。
本例的调用关系如下,区间右端均不包含:
sortRange(0, 5)├── sortRange(0, 2)│ ├── sortRange(0, 1) → 返回│ ├── sortRange(1, 2) → 返回│ └── 合并为 [2, 5]├── sortRange(2, 5)│ ├── sortRange(2, 3) → 返回│ ├── sortRange(3, 5) → 合并为 [1, 3]│ └── 合并为 [1, 3, 4]└── 合并为 [1, 2, 3, 4, 5]Java 按代码顺序执行,左侧递归完成后才执行右侧递归;这段代码没有并行启动两个任务。
这里拆的是下标范围,没有在每次递归时创建新的子数组。实际数据仍在同一个工作数组中。
三、两个有序段怎样合并
假设递归已经完成了左右两边,现在只需要合并 [2, 5] 和 [1, 3, 4]。
让 i 指向左段当前元素,j 指向右段当前元素,比较两者,把较小的那个写入缓冲区,然后只移动对应的指针。
| 左段当前值 | 右段当前值 | 取出谁 | 已写入缓冲区 |
|---|---|---|---|
| 2 | 1 | 右段的 1 | [1] |
| 2 | 3 | 左段的 2 | [1, 2] |
| 5 | 3 | 右段的 3 | [1, 2, 3] |
| 5 | 4 | 右段的 4 | [1, 2, 3, 4] |
| 5 | 已耗尽 | 左段剩余的 5 | [1, 2, 3, 4, 5] |
每次取出的元素,都是两个尚未处理部分中的最小值。因为两段各自有序,只看它们的开头就足够了。
任意一段耗尽后,另一段剩余元素已经有序,直接追加。随后把缓冲区中的这一段复制回工作数组,外层递归才能使用排好序的结果。
四、把分解和合并写成代码
下面是完整源码中的排序方法,省略了外层类和 main。入口 sortedCopy 返回一个排序后的副本,原数组保持原顺序。
public static int[] sortedCopy(int[] values) { if (values == null) { throw new IllegalArgumentException("values must not be null"); } int[] result = values.clone(); int[] buffer = new int[result.length]; sortRange(result, buffer, 0, result.length); return result;}
private static void sortRange(int[] values, int[] buffer, int left, int right) { if (right - left <= 1) return; int mid = left + (right - left) / 2; sortRange(values, buffer, left, mid); sortRange(values, buffer, mid, right);
int i = left; int j = mid; int k = left; while (i < mid && j < right) { if (values[i] <= values[j]) { buffer[k++] = values[i++]; } else { buffer[k++] = values[j++]; } } while (i < mid) buffer[k++] = values[i++]; while (j < right) buffer[k++] = values[j++]; for (int p = left; p < right; p++) values[p] = buffer[p];}buffer[k++] = values[i++] 的含义是:使用当前下标完成赋值,再分别把 k 和 i 加一。初学时也可以拆成三行阅读,不影响算法。
注意 k 从 left 开始,复制回去的范围也必须是 [left, right)。当前递归只负责这一段,不能顺便覆盖尚未处理的其他位置。
入口只创建一次缓冲区,所有递归调用复用它。由于合并按顺序发生,且只读写当前负责的区间,这样使用不会让不同调用互相覆盖未完成的工作。
五、相等时取左边有什么意义
合并条件写的是 values[i] <= values[j]。两边相等时,先取左侧元素。
为了看清区别,给两个相同数值标上身份:原来顺序是 2A 在 2B 之前,拆分后它们分别位于左右两段。相等时先取左边,就能让排序之后仍然是 2A, 2B。
这种保留相同排序键之间原有相对顺序的性质,叫作稳定性。例如订单先按创建时间排列,再稳定地按金额排序,相同金额的订单仍保持原来的时间顺序。
本例只存整数,看不出相同值的身份,但合并规则仍然是稳定的。如果改为严格小于号,相等时会先取右段,便不再保证这一性质。
六、时间和空间不能只看递归层数
数组每次大致对半拆,递归深度为 O(log n)。但排序时间不是 O(log n):同一层各个区间加起来要处理约 n 个元素,合并及复制的总工作量为 O(n)。
共有 O(log n) 层,每层 O(n),所以对 n >= 2,本实现的时间复杂度为 O(n log n)。即使输入已经有序,代码仍然拆分和合并,时间量级不变。
空间要看执行时同时占用的存储。长度为 n 的工作副本和缓冲区各占 O(n),同时存在的递归栈深度为 O(log n),合计为 O(n)。即便把返回副本视为输出空间单独计算,缓冲区仍然需要 O(n) 的辅助空间。
不能数出许多递归调用,就把它们的栈空间全部相加:已经返回的调用不再占用当前调用栈。也不能据此推断所有递归都只需要对数深度;每次只缩小一个元素的递归,可能达到线性深度。
七、运行并检查边界
下载完整 MergeSort.java,在文件所在目录运行:
javac -encoding UTF-8 MergeSort.javajava MergeSort预期输出:
[1, 2, 3, 4, 5][5, 2, 4, 1, 3]第一行是返回的有序副本,第二行是原数组。也可以下载整个系列的示例代码。
再检查空数组、单元素、重复元素和负数,例如 []、[7]、[3, 1, 3]、[-2, -8, 0]。预期分别为 []、[7]、[1, 3, 3]、[-8, -2, 0]。
排查错误时重点看三处:递归区间是否缩小;两段耗尽后的剩余元素是否追加;缓冲结果是否复制回当前区间。仅检查结果“看起来递增”还不够,也要确认没有丢失或重复元素。
八、练习:直接合并两个有序数组
先独立实现 merge(int[] a, int[] b),返回一个新数组,输入数组保持原样。这个练习暂时不需要递归,只使用刚学会的双指针合并。
输入 [1, 4, 4] 和 [2, 4, 6],预期得到 [1, 2, 4, 4, 4, 6];其中一个输入为空时,应返回另一个数组内容的副本。
提示:三个指针都从 0 开始;新数组长度为两个输入长度之和;主循环在两边都有元素时执行,之后追加余下部分。若两段长度分别为 m、n,你应能说明为什么总时间为 O(m + n)。
完成后,试着合上正文讲清“当前调用负责什么、下一次调用规模多大、什么时候返回”。这三个问题也是阅读树遍历和回溯代码的基础。接着进入下一篇:栈、队列与树。
If this article helped you, please share it with others!
Some information may be outdated






