本教程深入探讨了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;
}注意事项：
立即学习“Java免费学习笔记（深入）”；
- 此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
- 在主循环结束后，可能有两个数组或一个数组还有剩余元素。后续的while循环用于处理这些情况，确保所有剩余元素都被正确地复制到result数组中。
- 这种多指针比较的方法可以推广到合并N个已排序数组，但当N较大时，使用优先队列（最小堆）来管理N个数组的当前最小元素会是更优雅和高效的解决方案。
总结
本教程详细介绍了如何在Java中实现一个不依赖Arrays.copyOfRange的递归归并排序算法。通过自定义数组切片方法，我们能够更好地控制数组操作的细节。同时，教程还扩展了归并操作的应用，展示了如何高效地合并三个已排序的数组。理解这些底层实现有助于加深对排序算法的理解，并在特定场景下提供更灵活的解决方案。在实际开发中，虽然Arrays.copyOfRange等内置方法通常更优，但掌握手动实现的能力对于算法学习和性能调优至关重要。
