本教程深入探讨了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 original.length) { throw new IllegalArgumentException("起始索引超出数组范围。"); } if (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. 递归归并排序算法实现
有了自定义的数组切片方法，我们就可以着手实现递归的归并排序算法了。
闪念贝壳
闪念贝壳是一款AI 驱动的智能语音笔记，随时随地用语音记录你的每一个想法。
218 查看详情
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 original.length) { throw new IllegalArgumentException("起始索引超出数组范围。"); } if (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递归归并排序：手动数组切片与多数组合并策略的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/988129.html
微信扫一扫 
支付宝扫一扫 
