Recursive MergeSort 实现中的数组越界与临时数组长度错误修复-java教程-PHP中文网

Recursive MergeSort 实现中的数组越界与临时数组长度错误修复

本文详解递归归并排序（mergesort）实现中因临时数组长度计算错误导致的越界、填充异常及输出混乱问题，并提供完整修正代码与关键原理说明。

本文详解递归归并排序（mergesort）实现中因临时数组长度计算错误导致的越界、填充异常及输出混乱问题，并提供完整修正代码与关键原理说明。

在您提供的 Java 递归归并排序实现中，核心逻辑（分治结构、合并流程）基本正确，但存在一个致命的数组边界错误，直接导致输出异常：前几项看似有序、中间出现多个 0、后续又混杂未排序元素——这并非递归失效，而是 merge 方法中临时数组 temp 的容量与拷贝逻辑不匹配所致。

? 根本问题：临时数组长度错误

原代码中：

int temp[] = new int[high + 1];

该语句创建了一个长度为 high + 1 的数组（例如当 low=0, high=6 时，temp 长度为 7），看似足够，实则严重错误：

merge 操作仅处理子区间 [low, high]（共 high - low + 1 个元素）；
但 temp 却按 high + 1 分配——若 low > 0（如第二次递归调用 mergesort(arr, 4, 6)），high=6 仍分配长度为 7 的数组，而实际需容纳 3 个元素（索引 4~6）；

更严重的是，后续拷贝语句：

for (int i = 0; i <p>它无条件将整个 <code>temp</code>（长度 <code>high+1</code>）写回 <code>arr</code> 的<strong>起始位置 <code>arr[0]</code> 开始</strong>，而非目标区间 <code>[low, high]</code>！这会覆盖原数组前端有效数据，引入 <code>0</code>（<code>temp</code> 未赋值部分默认为 <code>0</code>），并破坏已排序段。</p>

✅ 正确修复方案

临时数组长度必须严格匹配待合并段长度：

int[] temp = new int[high - low + 1]; // ✅ 仅分配所需空间

合并结果应拷贝回原数组的对应区间 [low, high]，而非从 arr[0] 开始：

// 将 temp 中 [0, temp.length-1] 的元素，拷贝到 arr[low] ~ arr[high]
for (int i = 0; i

移除调试用的冗余打印（避免干扰逻辑验证）：
合并过程中的 System.out.print(...) 应删除或仅在调试时启用，否则输出混杂、难以定位问题。

? 完整修正代码（含注释）

import java.util.*;

public class Main {
    public static void merge(int[] arr, int low, int mid, int high) {
        // ✅ 正确：temp 长度 = 待合并元素总数
        int[] temp = new int[high - low + 1];
        int index = 0;
        int left = low;
        int right = mid + 1;

        // 归并两个已排序子数组
        while (left = high) return; // 基础情况：单元素或空区间
        int mid = low + (high - low) / 2; // ✅ 防止整数溢出（推荐写法）
        mergesort(arr, low, mid);
        mergesort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 46, 5, 8, 7, 6};
        System.out.println("Original: " + Arrays.toString(arr));
        mergesort(arr, 0, arr.length - 1);
        System.out.println("Sorted:   " + Arrays.toString(arr));
        // 输出：Sorted:   [2, 3, 5, 6, 7, 8, 46]
    }
}

⚠️ 注意事项与最佳实践

避免整数溢出：计算 mid 时建议用 low + (high - low) / 2 替代 (low + high) / 2，尤其在处理大数组时更安全。
空间局部性：temp 在每次 merge 中新建，虽简洁但非最优；生产环境可考虑复用全局临时数组以减少 GC 压力。
稳定性保证：当前实现中 if (arr[left] 使用 <code> 确保相等元素的相对顺序不变，维持归并排序的<strong>稳定性</strong>。
调试技巧：首次验证算法时，可添加日志打印 low, mid, high 及合并前后的子数组片段，而非全数组输出，避免信息过载。