大家平时写分治算法的时候，是不是经常觉得思路很清楚，结果一跑程序就各种离谱？尤其是像归并排序这种，代码看着没问题，但输出的数组乱七八糟。今天我专门说说一个特别容易踩的坑：在分解那一步，没有正确拷贝子数组，导致数据被污染。这个坑我当年也踩过，调试了很久，希望你看完能少走弯路。
一、从一次排序出错说起
前几天有个朋友让我帮他看代码，他写了一个归并排序，输入一个数组，输出结果总是比原数组多几个数字，有时候还会报数组越界。我一看，问题就出在“分解”那两个拷贝子数组的语句上。他用的是 Arrays.copyOfRange，结果结束索引写错了，导致左子数组丢了最后一个元素，右子数组却多了一个中间元素，而且最后一个元素不见了。
这种情况其实挺普遍的，尤其是新手。为什么？因为很多人在脑子里已经想清楚了“左边一段，右边一段”，但落实到代码时，容易把数组的起点、终点、长度绕晕。更严重的是，有些朋友为了省事，直接让左右两个变量指向同一个数组，想着“反正后面会递归”，结果数据互相修改，成了一锅粥。
所以今天咱们就围绕这个点好好聊一聊。
二、分治的基本套路
2.1 分治三步走
分治这东西，说白了三步：第一步，把大问题拆成若干小问题；第二步，每个小问题单独解决；第三步，把解决好的小问题合并成完整答案。这就像收拾一个乱房间，你不会想着一下全收拾完，而是先把衣服、书、杂物各归一类，然后分别整理，最后再摆放整齐。是不是很生活化？
2.2 归并排序是典型代表
归并排序就是分治思想最经典的代表。每次把数组从中间一分为二，分别排序，然后合并两个有序数组。问题来了，你一分为二之后，总得把这两部分的数据“拿”出来吧？这时候就需要正确地把子数组复制出来。复制不好，后面的合并部分就全乱套了。所以，拷贝这个动作看似简单，其实是分治的地基。
三、常见错误：分解时没有正确拷贝子数组
3.1 错误示例代码
下面这段代码，就是典型错误。我用 Java 写一个归并排序，故意把 copyOfRange 的边界写错。咱们仔细看注释。
// 技术栈：Java
import java.util.Arrays;
public class MergeSortWrong {
/**
* 错误的归并排序
*
* @param arr 待排序数组
* @param start 起始下标（包含）
* @param end 结束下标（不包含） —— 注意这个约定！
*/
public static void mergeSort(int[] arr, int start, int end) {
// 如果区间内元素个数小于等于1，直接返回
if (end - start <= 1) {
return;
}
// 取中点，把区间分成 [start, mid) 和 [mid, end)
int mid = start + (end - start) / 2;
// 错误点在这里！！！
// 想拷贝左半部分 [start, mid)，但 copyOfRange 的 to 参数是排他性的，
// 要包含 mid-1，得写成 mid，这里却写成了 mid - 1，导致少了一个元素。
int[] left = Arrays.copyOfRange(arr, start, mid - 1); // 错！少了一个元素
// 拷贝右半部分 [mid, end)，正确写法应该是 copyOfRange(arr, mid, end)
// 这里却写成了 copyOfRange(arr, mid + 1, end)，直接跳过了第一个元素。
int[] right = Arrays.copyOfRange(arr, mid + 1, end); // 错！丢了一个元素
// 递归排序左右子数组
mergeSort(left, 0, left.length);
mergeSort(right, 0, right.length);
// 合并两个有序子数组回原数组的 [start, end) 区间
merge(left, right, arr, start);
}
/**
* 合并两个有序数组，结果写到 src 的 startIndex 开始的位置
*/
private static void merge(int[] left, int[] right, int[] src, int startIndex) {
int i = 0, j = 0, k = startIndex;
// 谁小先把谁放进去
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
src[k++] = left[i++];
} else {
src[k++] = right[j++];
}
}
// 把剩余部分拷贝过去
while (i < left.length) {
src[k++] = left[i++];
}
while (j < right.length) {
src[k++] = right[j++];
}
}
public static void main(String[] args) {
int[] arr = {4, 2, 7, 1, 9, 3};
System.out.println("排序前: " + Arrays.toString(arr));
mergeSort(arr, 0, arr.length);
System.out.println("排序后: " + Arrays.toString(arr));
}
}
注意看，上面这个代码里，左半部分我写得是 copyOfRange(arr, start, mid - 1)。如果 mid 和 start 很接近，可能直接抛异常；就算不抛，左子数组也会少一个元素。右半部分呢，copyOfRange(arr, mid + 1, end)，把 mid 那个元素给弄丢了。这样左右子数组加起来，元素个数比原来的少，而且数据还不完整。合并时，你根本不知道哪些数据被弄丢了，得到的结果自然就是乱序。
3.2 为什么会导致数据污染
咱们静下心分析一下。数组的区间我们约定的是左闭右开，也就是 [start, end)。用 copyOfRange 复制时，第一个参数是要复制的数组，第二个参数是起始下标（包含），第三个参数是结束下标（不包含）。你想复制左半部分 [start, mid)，就应该写 Arrays.copyOfRange(arr, start, mid)，结束下标写成 mid，这样就自动包含 mid - 1，不包含 mid。右半部分 [mid, end)，就应该写 Arrays.copyOfRange(arr, mid, end)。
但错误代码里，左半部分用了 mid - 1，结束下标成了 mid - 1，等于复制了 [start, mid-1)，少了一个元素；右半部分用了 mid + 1，复制了 [mid+1,end)，也少了一个元素。结果就是原来数组中间位置的数据“凭空消失”了。后面合并时，这两个残缺的子数组被当作完整数据用于排序，再写回原数组，原数组自然就被污染了。这就是典型的“分解时未正确拷贝子数组导致数据污染”。
3.3 正确示例代码
那正确写法是什么呢？很简单，把边界写对就行。我再贴一个正确版本，顺便演示一下另一个拷贝方式 System.arraycopy 的用法，它同样需要注意位置和长度。
// 技术栈：Java
import java.util.Arrays;
public class MergeSortFixed {
/**
* 正确的归并排序
* 统一使用左闭右开区间
*
* @param arr 待排序数组
* @param start 起始下标（包含）
* @param end 结束下标（不包含）
*/
public static void mergeSort(int[] arr, int start, int end) {
// 只有一个元素或者没有元素，直接返回
if (end - start <= 1) {
return;
}
int mid = start + (end - start) / 2;
// 正确拷贝左子数组 [start, mid)
int[] left = Arrays.copyOfRange(arr, start, mid);
// 正确拷贝右子数组 [mid, end)
int[] right = Arrays.copyOfRange(arr, mid, end);
// 递归处理左右两边
mergeSort(left, 0, left.length);
mergeSort(right, 0, right.length);
// 合并回原数组
merge(left, right, arr, start);
}
/**
* 合并两个有序数组到 src 的 startIndex 开始的位置
*/
private static void merge(int[] left, int[] right, int[] src, int startIndex) {
int i = 0, j = 0, k = startIndex;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
src[k++] = left[i++];
} else {
src[k++] = right[j++];
}
}
// 直接使用 System.arraycopy 拷贝剩余部分，避免手动循环
if (i < left.length) {
System.arraycopy(left, i, src, k, left.length - i);
}
if (j < right.length) {
System.arraycopy(right, j, src, k, right.length - j);
}
}
public static void main(String[] args) {
int[] arr = {4, 2, 7, 1, 9, 3};
System.out.println("排序前: " + Arrays.toString(arr));
mergeSort(arr, 0, arr.length);
System.out.println("排序后: " + Arrays.toString(arr));
}
}
这里需要额外说一句，System.arraycopy 的五个参数分别是：源数组、源数组起始位置、目标数组、目标数组起始位置、要复制的长度。很多人会把长度算错，比如把 left.length - i 写成 left.length，那就会越界。所以不管是 copyOfRange 还是 arraycopy，边界和长度永远是分治拷贝的命根子。
另外，有的朋友可能会问，为什么我不直接对原数组片段排序？就像 Python 里可以用切片，Java 里没有切片操作，只能拷贝。拷贝时如果怕出错，其实也可以用 System.arraycopy 手动控制，但是要小心别让源和目标重叠。不过我们这里拷贝到新数组，不存在重叠问题，相对安全。
四、调试与规避经验
4.1 打印中间结果
当你发现排序结果不对时，第一招就是打印每次分解后的子数组。具体做法是在归并排序入口处加上一行日志，把 start、mid、end 以及拷贝出来的左右数组都打出来。下面是一个加了日志的调试版本。
// 技术栈：Java
import java.util.Arrays;
public class MergeSortDebug {
public static void mergeSort(int[] arr, int start, int end, int depth) {
if (end - start <= 1) {
return;
}
int mid = start + (end - start) / 2;
// 打印当前要处理的区间
System.out.printf("深度%d: 处理 [%d, %d), mid=%d%n", depth, start, end, mid);
int[] left = Arrays.copyOfRange(arr, start, mid);
int[] right = Arrays.copyOfRange(arr, mid, end);
// 打印拷贝出来的子数组
System.out.printf("左子数组: %s%n", Arrays.toString(left));
System.out.printf("右子数组: %s%n", Arrays.toString(right));
mergeSort(left, 0, left.length, depth + 1);
mergeSort(right, 0, right.length, depth + 1);
merge(left, right, arr, start);
// 打印合并结果
System.out.printf("合并后: %s%n", Arrays.toString(Arrays.copyOfRange(arr, start, end)));
}
private static void merge(int[] left, int[] right, int[] src, int startIndex) {
int i = 0, j = 0, k = startIndex;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
src[k++] = left[i++];
} else {
src[k++] = right[j++];
}
}
if (i < left.length) {
System.arraycopy(left, i, src, k, left.length - i);
}
if (j < right.length) {
System.arraycopy(right, j, src, k, right.length - j);
}
}
public static void main(String[] args) {
int[] arr = {4, 2, 7, 1, 9, 3};
mergeSort(arr, 0, arr.length, 0);
}
}
运行这个调试版本，你会很清晰地看到左子数组和右子数组里到底有哪些元素。如果拷贝边界写错，比如左子数组少了最后一个，右子数组少了第一个，日志会立刻暴露问题。这种“眼见为实”的调试方式，比分屏瞪眼强一百倍。
4.2 使用断言检测
除了打印日志，还可以在合并前加一个断言，保证左子数组长度加右子数组长度，恰好等于当前区间的长度。这个检查能在第一时间拦住错误。下面是个简单示范。
// 技术栈：Java
// 在归并排序的递归函数里加入断言
assert left.length + right.length == end - start : "子数组长度和与区间长度不一致！";
比如在错误代码中，左子数组和右子数组各少一个，那么长度之和就是 (mid - start - 1) + (end - mid - 1) = end - start - 2，不等于 end - start，断言失败。运行时会抛出 AssertionError，提醒你数据拷贝有问题。当然，Java 默认关闭断言，你需要用 -ea 参数开启。在 IDEA 里也可以配置 VM options。这个技巧对归并排序这类分治算法非常实用。
4.3 小规模数据测试
还有一招，就是永远不要一开始就拿几十个元素的大数组来试。用只有 3、4 个元素的小数组，比如 {4, 2, 7, 1}，手动算一算。我会在草稿纸上写清楚每一步的区间、mid、左右子数组，然后对比代码输出。小数据的问题很容易暴露，因为你的脑子还能跟上计算的节奏。等小数据完全正确了，再换随机大数组做压力测试，这时候就算出错，也更可能是一些极端情况，而不是基础拷贝问题。
4.4 养成区间约定一致的习惯
这一点特别重要。有的朋友喜欢用左闭右闭，有的喜欢用左闭右开，这两种都没问题，但一定要在全代码中保持一致。我个人的建议是统一用左闭右开，也就是 [start, end)，因为 Java 里很多 API 都是这个习惯，比如 Arrays.copyOfRange 和 String.substring 都是左闭右开。这样你不用每写一次就纠结一次“这里要不要减一”。习惯一致了，边界错误至少能减少一半。
五、应用场景与技术优缺点
5.1 应用场景
分治思想在编程里到处都是。除了归并排序，快速排序、二分查找、大整数乘法、棋盘覆盖、最近点对问题，全都是分治的“粉丝”。以归并排序为例，它特别适合对链表排序、外部排序，以及需要稳定排序的场景。比如你要排序的数据太大，内存装不下，分治就可以先把数据切块，分别排序，再归并到磁盘上，这就是外部排序的原理。另外，在分布式系统里，把大任务拆给多台机器做，也是分治思想的表现。
5.2 技术优缺点
分治技术的优点很突出：思路清晰，把复杂问题拆成简单小问题，代码写起来符合直觉；而且非常适合并行化，因为每个子问题相对独立，可以同时处理。缺点也很明显：递归调用会带来函数栈开销；每层都需要额外的存储空间，比如归并排序的空间复杂度是 O(n)，对内存不友好；另外，分解和合并阶段特别容易出边界错误，对初学者的细心程度是个考验。我们今天聊的“拷贝子数组污染”其实就是缺点的一个真实写照。
六、注意事项与总结
6.1 注意事项
- 使用
Arrays.copyOfRange时，永远记住结束下标是“不包含”的。想复制[a, b)，就写copyOfRange(arr, a, b)，不要手滑多写或少写一个。 - 不要用同一个数组对象同时充当左子数组和右子数组。有些朋友投机取巧，推出一个“视图”，结果修改一个另一个也跟着变，数据彻底乱套。
- 递归前一定要确认子数组的长度是正确的。可以在递归前打印长度，或者用断言检查，确保左右长度之和等于父区间长度。
- 命名要清晰。别把区间变量名字起得太像，
start、end、mid写清楚，不容易犯迷糊。 - 测试用小数数组起步，再过渡到随机大数组。
6.2 总结
今天咱们围绕分治算法里一个非常常见的坑——分解时没有正确拷贝子数组——说了不少。从错误代码到正确代码，从打印日志到断言调试，整个流程其实就是每个开发者都会经历的：先踩坑，再分析，最后总结出一套规避方法。分治算法本身并不神秘，难的是把边界条件、拷贝时机这些细节处理好。希望你在以后写归并排序或者其他分治算法时，心里能绷住一根弦：拷贝子数组时，多看一眼索引，多想一遍区间开闭，数据污染这种问题就会离你远远的。
评论
围绕“分治常见错误：分解时未正确拷贝子数组导致数据污染，调试与规避经验分享”参与讨论