本教程深入探讨了java中递归归并排序的实现细节，特别关注了如何在不依赖`java.util.arrays`包的情况下，手动实现数组的子范围复制功能，以替代`arrays.copyofrange`。此外，文章还将详细介绍如何扩展传统的两路归并操作，实现对三个已排序数组的高效合并，并提供相应的代码示例与注意事项，旨在帮助开发者全面理解和掌握归并排序及其变体。
1. 归并排序概述
归并排序（Merge Sort）是一种高效的、基于比较的排序算法，它采用了分治（Divide and Conquer）策略。其基本思想是将待排序的数组递归地分成两半，直到每个子数组只包含一个元素（自然有序），然后将这些子数组两两合并，每次合并都使子数组变得有序，最终合并成一个完全有序的数组。
归并排序的两个核心步骤是：
分（Divide）：将一个包含 n 个元素的数组分成两个各包含 n/2 个元素的子数组。治（Conquer）：递归地对这两个子数组进行排序。合（Combine）：将两个已排序的子数组合并成一个已排序的数组。
2. 手动实现数组子范围复制
在Java中，Arrays.copyOfRange(original, from, to) 方法可以方便地复制数组的指定范围。然而，在某些场景下，我们可能需要避免使用标准库中的特定包，或者希望深入理解底层实现。以下是如何手动实现一个功能类似的 copyArray 方法。
Arrays.copyOfRange(original, from, to) 的行为是复制 original 数组中从 from（包含）到 to（不包含）索引的元素。我们需要在手动实现中遵循相同的逻辑。
立即学习“Java免费学习笔记（深入）”；
/** * 手动复制数组指定范围的元素。 * * @param original 原始数组。 * @param from 起始索引（包含）。 * @param to 结束索引（不包含）。 * @return 包含原始数组指定范围元素的新数组。 * @throws IllegalArgumentException 如果from或to参数无效。 */private static int[] copyArray(int[] original, int from, int to) { // 参数校验：确保起始索引和结束索引的有效性 if (from original.length || from > to) { throw new IllegalArgumentException( String.format("无效的数组复制范围：from=%d, to=%d, original.length=%d", from, to, original.length)); } int[] result = new int[to - from]; // 新数组的长度为 to - from for (int i = from; i < to; i++) { result[i - from] = original[i]; // 将原始数组的元素复制到新数组的相应位置 } return result;}
这个 copyArray 方法实现了与 Arrays.copyOfRange 相同的功能，能够根据指定的起始和结束索引（结束索引不包含）创建一个新的数组。
3. 递归归并排序的实现
有了 copyArray 方法，我们就可以实现不依赖 java.util.Arrays 包的递归归并排序了。
PicDoc
AI文本转视觉工具，1秒生成可视化信息图
6214 查看详情
3.1 mergeSort 函数
mergeSort 函数是归并排序的核心，它负责递归地将数组分解，然后调用 merge 函数进行合并。
/** * 对给定数组进行递归归并排序。 * * @param A 待排序的数组。 */static void mergeSort(int[] A) { // 递归终止条件：如果数组长度小于或等于1，则认为它已经有序 if (A.length > 1) { int mid = A.length / 2; // 计算数组中点 // 使用自定义的 copyArray 方法创建左右子数组 // 左子数组包含从索引 0 到 mid-1 的元素 int[] leftArray = copyArray(A, 0, mid); // 右子数组包含从索引 mid 到 A.length-1 的元素 int[] rightArray = copyArray(A, mid, A.length); // 递归地对左右子数组进行排序 mergeSort(leftArray); mergeSort(rightArray); // 将已排序的左右子数组合并回原始数组 A merge(A, leftArray, rightArray); }}
注意事项：
copyArray(A, 0, mid) 复制了 A 中从索引 0 到 mid-1 的 mid 个元素。copyArray(A, mid, A.length) 复制了 A 中从索引 mid 到 A.length-1 的 A.length – mid 个元素。merge 函数负责将两个已排序的子数组合并到一个目标数组中，这里目标数组是 A。
3.2 merge 函数（两路归并）
merge 函数是归并排序的另一个关键部分，它将两个已排序的数组合并成一个更大的已排序数组。
/** * 将两个已排序的子数组合并到一个目标数组中。 * * @param targetArray 目标数组，合并后的结果将存储在此数组中。 * @param leftArray 第一个已排序的子数组。 * @param rightArray 第二个已排序的子数组。 */static void merge(int[] targetArray, int[] leftArray, int[] rightArray) { int i = 0; // targetArray 的当前索引 int leftPtr = 0; // leftArray 的当前索引 int rightPtr = 0; // rightArray 的当前索引 // 当两个子数组都还有元素时，比较它们的首元素并将较小的元素放入 targetArray while (leftPtr < leftArray.length && rightPtr < rightArray.length) { if (leftArray[leftPtr] < rightArray[rightPtr]) { targetArray[i++] = leftArray[leftPtr++]; } else { targetArray[i++] = rightArray[rightPtr++]; } } // 将 leftArray 中剩余的元素复制到 targetArray while (leftPtr < leftArray.length) { targetArray[i++] = leftArray[leftPtr++]; } // 将 rightArray 中剩余的元素复制到 targetArray while (rightPtr < rightArray.length) { targetArray[i++] = rightArray[rightPtr++]; }}
4. 实现三路归并函数
除了传统的两路归并，有时我们可能需要将多个（例如三个）已排序的数组合并成一个。以下是实现一个 mergeArrays3 函数，用于合并三个已排序的数组 a, b, c。
为了高效地合并三个数组，我们可以使用三个指针分别指向每个数组的当前元素，每次比较这三个指针所指向的元素，将最小的元素放入结果数组，并移动相应数组的指针。当某个数组的元素耗尽时，我们可以将其“当前元素”视为一个极大的值（例如 Integer.MAX_VALUE），这样它就不会再被选为最小元素，直到所有实际元素都被处理完毕。
/** * 将三个已排序的数组合并成一个已排序的新数组。 * * @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 是结果数组的指针 // 只要任一数组还有未合并的元素，就继续循环 while (i < a.length || j < b.length || l < c.length) { // 获取当前指针指向的元素值，如果数组已耗尽，则使用 Integer.MAX_VALUE 作为哨兵值 int valA = (i < a.length) ? a[i] : Integer.MAX_VALUE; int valB = (j < b.length) ? b[j] : Integer.MAX_VALUE; int valC = (l < c.length) ? c[l] : Integer.MAX_VALUE; // 找到三个值中的最小值，并将其放入结果数组 if (valA <=
以上就是Java递归归并排序：手动数组切片与多数组合并教程的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/988533.html
微信扫一扫 
支付宝扫一扫 
