无Java包依赖实现递归MergeSort及三数组合并函数

需求说明 #

• 替换原归并排序代码中的Arrays.copyOfRange方法，手动实现数组区间复制，不能依赖任何Java工具包，同时保留mergeSort(int[] A)和merge(int[] a, int[] l, int[] r)的函数结构。
• 修正并实现接收三个数组参数的合并函数mergeArrays3。

问题分析 #

1. 原代码中Arrays.copyOfRange的使用存在范围错误：copyOfRange是左闭右开区间，原代码里的0到q-1会少复制一个元素，正确的左数组应该是从0到q，右数组从q到数组末尾。
2. 自行编写的mergeArrays3存在逻辑错误：索引混用（比如用i访问c数组）、多条件判断导致重复赋值，无法正确找出三个数组中的当前最小值。

解决方案 #

1. 手动实现数组区间复制 #

编写无依赖的copyArrayRange方法，模拟Arrays.copyOfRange的左闭右开逻辑：

// 手动实现数组区间复制，左闭右开：[start, end)
private static int[] copyArrayRange(int[] source, int start, int end) {
    int length = end - start;
    int[] result = new int[length];
    for (int i = 0; i < length; i++) {
        result[i] = source[start + i];
    }
    return result;
}

2. 修正三数组合并函数 #

重新梳理逻辑：当三个数组都有未处理元素时，逐一比较找出当前最小值，放入结果数组并移动对应索引；之后依次处理剩余元素：

public static int[] mergeArrays3(int[] a, int[] b, int[] c) {
    int[] result = new int[a.length + b.length + c.length];
    int i = 0, j = 0, k = 0, idx = 0;

    // 同时处理三个数组都有元素的情况
    while (i < a.length && j < b.length && k < c.length) {
        int minVal = Math.min(Math.min(a[i], b[j]), c[k]);
        if (minVal == a[i]) {
            result[idx++] = a[i++];
        } else if (minVal == b[j]) {
            result[idx++] = b[j++];
        } else {
            result[idx++] = c[k++];
        }
    }

    // 处理两两数组的剩余元素
    while (i < a.length && j < b.length) {
        result[idx++] = a[i] < b[j] ? a[i++] : b[j++];
    }
    while (i < a.length && k < c.length) {
        result[idx++] = a[i] < c[k] ? a[i++] : c[k++];
    }
    while (j < b.length && k < c.length) {
        result[idx++] = b[j] < c[k] ? b[j++] : c[k++];
    }

    // 处理单个数组的剩余元素
    while (i < a.length) result[idx++] = a[i++];
    while (j < b.length) result[idx++] = b[j++];
    while (k < c.length) result[idx++] = c[k++];

    return result;
}

完整修正后的代码 #

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class MergeSort {

    public static void main(String[] args) throws IOException {
        BufferedReader R = new BufferedReader(new InputStreamReader(System.in));
        int arraySize = Integer.parseInt(R.readLine());
        int[] inputArray = new int[arraySize];
        for (int i = 0; i < arraySize; i++) {
            inputArray[i] = Integer.parseInt(R.readLine());
        }
        mergeSort(inputArray);

        for (int j = 0; j < inputArray.length; j++) {
            System.out.println(inputArray[j]);
        }
    }

    static void mergeSort(int[] A) {
        if (A.length > 1) {
            int q = A.length / 2;
            // 手动复制数组区间，替代Arrays.copyOfRange
            int[] leftArray = copyArrayRange(A, 0, q);
            int[] rightArray = copyArrayRange(A, q, A.length);

            mergeSort(leftArray);
            mergeSort(rightArray);

            merge(A, leftArray, rightArray);
        }
    }

    static void merge(int[] a, int[] l, int[] r) {
        int totElem = l.length + r.length;
        int i = 0, li = 0, ri = 0;
        while (i < totElem) {
            if (li < l.length && ri < r.length) {
                if (l[li] < r[ri]) {
                    a[i++] = l[li++];
                } else {
                    a[i++] = r[ri++];
                }
            } else {
                if (li >= l.length) {
                    while (ri < r.length) {
                        a[i++] = r[ri++];
                    }
                }
                if (ri >= r.length) {
                    while (li < l.length) {
                        a[i++] = l[li++];
                    }
                }
            }
        }
    }

    // 手动实现数组区间复制，左闭右开：[start, end)
    private static int[] copyArrayRange(int[] source, int start, int end) {
        int length = end - start;
        int[] result = new int[length];
        for (int i = 0; i < length; i++) {
            result[i] = source[start + i];
        }
        return result;
    }

    // 修正后的三数组合并函数
    public static int[] mergeArrays3(int[] a, int[] b, int[] c) {
        int[] result = new int[a.length + b.length + c.length];
        int i = 0, j = 0, k = 0, idx = 0;

        // 同时处理三个数组都有元素的情况
        while (i < a.length && j < b.length && k < c.length) {
            int minVal = Math.min(Math.min(a[i], b[j]), c[k]);
            if (minVal == a[i]) {
                result[idx++] = a[i++];
            } else if (minVal == b[j]) {
                result[idx++] = b[j++];
            } else {
                result[idx++] = c[k++];
            }
        }

        // 处理两两数组的剩余元素
        while (i < a.length && j < b.length) {
            result[idx++] = a[i] < b[j] ? a[i++] : b[j++];
        }
        while (i < a.length && k < c.length) {
            result[idx++] = a[i] < c[k] ? a[i++] : c[k++];
        }
        while (j < b.length && k < c.length) {
            result[idx++] = b[j] < c[k] ? b[j++] : c[k++];
        }

        // 处理单个数组的剩余元素
        while (i < a.length) result[idx++] = a[i++];
        while (j < b.length) result[idx++] = b[j++];
        while (k < c.length) result[idx++] = c[k++];

        return result;
    }
}

内容的提问来源于stack exchange，提问作者memo