Java递归归并排序：切片与合并技巧解析

来到golang学习网的大家，相信都是编程学习爱好者，希望在这里学习文章相关编程知识。下面本篇文章就来带大家聊聊《Java递归归并排序：数组切片与合并技巧》，介绍一下，希望对大家的知识积累有所帮助，助力实战开发！

本教程深入探讨了Java中递归归并排序的实现细节，特别关注如何在不依赖`Arrays.copyOfRange`等内置工具包的情况下进行数组切片操作。文章提供了自定义的数组复制方法，并详细讲解了双数组和三数组合并函数的实现逻辑，旨在帮助开发者构建高效且可控的排序算法，并扩展其在多数据源合并场景下的应用。

1. 归并排序概述

归并排序（Merge Sort）是一种基于分治策略的排序算法。其核心思想是将一个大数组递归地分解为两个子数组，直到子数组只包含一个元素（自然有序），然后将这些子数组两两合并，每次合并都保证结果有序，最终得到一个完全有序的数组。

2. 自定义数组切片实现（替代 Arrays.copyOfRange）

在标准Java库中，Arrays.copyOfRange提供了一种便捷的方式来截取数组的一部分。然而，在某些场景下，我们可能需要避免使用外部包，或者希望更深入理解其底层机制。以下是手动实现数组切片功能的方法：

/**
 * 自定义数组切片方法，模拟 Arrays.copyOfRange 的功能。
 * 创建一个新数组，包含原数组从指定起始索引到结束索引（不包含）的元素。
 *
 * @param original 原始数组
 * @param from 起始索引（包含）
 * @param to 结束索引（不包含）
 * @return 包含指定范围元素的新数组
 * @throws IllegalArgumentException 如果 from 或 to 超出数组边界，或 from > to
 */
private static int[] copyArray(int[] original, int from, int to) {
    if (original == null) {
        throw new IllegalArgumentException("原始数组不能为null。");
    }
    if (from < 0 || from > original.length) {
        throw new IllegalArgumentException("起始索引超出数组范围。");
    }
    if (to < 0 || to > original.length) {
        throw new IllegalArgumentException("结束索引超出数组范围。");
    }
    if (from > to) {
        throw new IllegalArgumentException("起始索引不能大于结束索引。");
    }

    int[] result = new int[to - from];
    for (int i = from; i < to; i++) {
        result[i - from] = original[i];
    }
    return result;
}

注意事项：

• 此copyArray方法提供了基本的边界检查，以确保索引的有效性。在实际应用中，应根据需求进一步完善错误处理机制。
• 这种手动复制方式在性能上通常会略低于JVM高度优化的Arrays.copyOfRange或System.arraycopy，但对于理解算法原理和避免外部依赖是有效的。

3. 递归归并排序算法实现

有了自定义的数组切片方法，我们就可以着手实现递归的归并排序算法了。

public class MergeSort {

    // 主函数，用于测试归并排序
    public static void main(String[] args) throws IOException {
        // 示例输入，实际应用中可从控制台或文件读取
        int[] inputArray = {5, 2, 4, 6, 1, 3, 2, 6};
        System.out.println("原始数组: " + Arrays.toString(inputArray));

        mergeSort(inputArray);

        System.out.println("排序后数组: " + Arrays.toString(inputArray));

        // 示例：合并三个数组
        int[] arr1 = {1, 3, 5, 7};
        int[] arr2 = {2, 4, 6, 8};
        int[] arr3 = {0, 9, 10};
        System.out.println("合并三个数组: " + Arrays.toString(arr1) + ", " + Arrays.toString(arr2) + ", " + Arrays.toString(arr3));
        int[] mergedThree = mergeArrays3(arr1, arr2, arr3);
        System.out.println("合并结果: " + Arrays.toString(mergedThree));
    }

    /**
     * 递归归并排序主方法。
     * 对给定的数组进行原地排序。
     *
     * @param A 待排序的整数数组
     */
    static void mergeSort(int[] A) {
        if (A.length > 1) {
            int mid = A.length / 2;

            // 使用自定义的 copyArray 进行数组切片
            // leftArray 包含从 0 到 mid-1 的元素
            int[] leftArray = copyArray(A, 0, mid);
            // rightArray 包含从 mid 到 A.length-1 的元素
            int[] rightArray = copyArray(A, mid, A.length);

            mergeSort(leftArray);  // 递归排序左半部分
            mergeSort(rightArray); // 递归排序右半部分

            merge(A, leftArray, rightArray); // 合并已排序的左右子数组
        }
    }

    /**
     * 合并两个已排序的子数组到一个主数组中。
     *
     * @param targetArray 目标数组，用于存放合并后的结果
     * @param left 子数组L
     * @param right 子数组R
     */
    static void merge(int[] targetArray, int[] left, int[] right) {
        int i = 0; // 指向 targetArray 的当前位置
        int li = 0; // 指向 left 数组的当前位置
        int ri = 0; // 指向 right 数组的当前位置

        // 当左右两个子数组都有元素时，比较并选择较小的元素放入 targetArray
        while (li < left.length && ri < right.length) {
            if (left[li] <= right[ri]) { // 注意使用 <= 保证稳定性
                targetArray[i++] = left[li++];
            } else {
                targetArray[i++] = right[ri++];
            }
        }

        // 将 left 数组中剩余的元素复制到 targetArray
        while (li < left.length) {
            targetArray[i++] = left[li++];
        }

        // 将 right 数组中剩余的元素复制到 targetArray
        while (ri < right.length) {
            targetArray[i++] = right[ri++];
        }
    }

    // ... (copyArray 方法定义在此处或上方)
    private static int[] copyArray(int[] original, int from, int to) {
        // ... (同上方 copyArray 实现)
        if (original == null) {
            throw new IllegalArgumentException("原始数组不能为null。");
        }
        if (from < 0 || from > original.length) {
            throw new IllegalArgumentException("起始索引超出数组范围。");
        }
        if (to < 0 || to > original.length) {
            throw new IllegalArgumentException("结束索引超出数组范围。");
        }
        if (from > to) {
            throw new IllegalArgumentException("起始索引不能大于结束索引。");
        }

        int[] result = new int[to - from];
        for (int i = from; i < to; i++) {
            result[i - from] = original[i];
        }
        return result;
    }
}

代码解析与注意事项：

• mergeSort函数首先检查数组长度，如果大于1，则将其一分为二。mid变量用于确定分割点。
• copyArray(A, 0, mid)用于创建左半部分数组，范围是[0, mid)。
• copyArray(A, mid, A.length)用于创建右半部分数组，范围是[mid, A.length)。
• merge函数负责将两个已排序的子数组left和right合并回targetArray。它通过三个指针i, li, ri来完成，分别跟踪targetArray、left和right的当前位置。
• 在合并过程中，总是将left和right中较小的元素放入targetArray。当其中一个子数组遍历完毕后，将另一个子数组中剩余的所有元素直接复制到targetArray。

4. 扩展应用：三数组合并函数 mergeArrays3

合并三个或更多已排序的数组是归并操作的自然扩展。虽然可以多次调用双数组合并函数，但直接实现一个多数组合并函数在某些情况下可能更直观或更高效。以下是合并三个已排序数组的实现：

    /**
     * 合并三个已排序的数组到一个新数组中。
     *
     * @param a 第一个已排序数组
     * @param b 第二个已排序数组
     * @param c 第三个已排序数组
     * @return 包含所有元素且已排序的新数组
     */
    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, l = 0, k = 0; // i, j, l 分别是 a, b, c 的指针；k 是 result 的指针

        // 当三个数组都有元素时，比较并选择最小的元素放入结果数组
        while (i < a.length && j < b.length && l < c.length) {
            if (a[i] <= b[j] && a[i] <= c[l]) {
                result[k++] = a[i++];
            } else if (b[j] <= a[i] && b[j] <= c[l]) {
                result[k++] = b[j++];
            } else { // c[l] 最小
                result[k++] = c[l++];
            }
        }

        // 处理剩余的两个数组（例如，a 和 b 还有元素，c 已遍历完）
        while (i < a.length && j < b.length) {
            if (a[i] <= b[j]) {
                result[k++] = a[i++];
            } else {
                result[k++] = b[j++];
            }
        }

        while (i < a.length && l < c.length) {
            if (a[i] <= c[l]) {
                result[k++] = a[i++];
            } else {
                result[k++] = c[l++];
            }
        }

        while (j < b.length && l < c.length) {
            if (b[j] <= c[l]) {
                result[k++] = b[j++];
            } else {
                result[k++] = c[l++];
            }
        }

        // 处理只剩下一个数组的情况
        while (i < a.length) {
            result[k++] = a[i++];
        }
        while (j < b.length) {
            result[k++] = b[j++];
        }
        while (l < c.length) {
            result[k++] = c[l++];
        }

        return result;
    }

代码解析与注意事项：

• mergeArrays3函数使用四个指针：i, j, l分别跟踪a, b, c数组的当前位置，k跟踪result数组的当前位置。
• 核心逻辑是while (i < a.length && j < b.length && l < c.length)循环，它在三个数组都有元素时，比较a[i], b[j], c[l]，将最小的元素放入result数组，并移动相应数组的指针。
• 在主循环结束后，可能有两个数组或一个数组还有剩余元素。后续的while循环用于处理这些情况，确保所有剩余元素都被正确地复制到result数组中。
• 这种多指针比较的方法可以推广到合并N个已排序数组，但当N较大时，使用优先队列（最小堆）来管理N个数组的当前最小元素会是更优雅和高效的解决方案。

总结

本教程详细介绍了如何在Java中实现一个不依赖Arrays.copyOfRange的递归归并排序算法。通过自定义数组切片方法，我们能够更好地控制数组操作的细节。同时，教程还扩展了归并操作的应用，展示了如何高效地合并三个已排序的数组。理解这些底层实现有助于加深对排序算法的理解，并在特定场景下提供更灵活的解决方案。在实际开发中，虽然Arrays.copyOfRange等内置方法通常更优，但掌握手动实现的能力对于算法学习和性能调优至关重要。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《Java递归归并排序：切片与合并技巧解析》文章吧，也可关注golang学习网公众号了解相关技术文章。