本文深入探讨了在java中递归实现归并排序的方法，特别关注如何在不依赖`java.util.arrays.copyofrange`等标准库函数的情况下，手动实现数组分片操作。同时，文章详细介绍了标准的二路合并算法，并提供了一种健壮的三路合并函数的实现，旨在帮助开发者掌握底层数组操作和多路数据流的合并技巧。
1. 归并排序概述
归并排序（Merge Sort）是一种高效的、基于比较的排序算法，其核心思想是分治法。它将一个未排序的数组递归地分成两半，直到每个子数组只有一个元素（自然有序），然后将这些子数组两两合并，每次合并都使子数组有序，最终合并成一个完全有序的数组。归并排序具有稳定的特性，并且时间复杂度在所有情况下都保持O(n log n)。
2. 递归实现归并排序 (MergeSort)
归并排序的递归实现主要包含两个部分：mergeSort 函数用于递归地将数组分成更小的部分，以及 merge 函数用于合并两个已排序的子数组。
2.1. 无包依赖的数组分片：手动实现 copyOfRange
在Java中，java.util.Arrays.copyOfRange(array, from, to) 是一个非常方便的工具，用于从现有数组中截取一个子范围并创建一个新数组。然而，在某些场景下，例如要求完全不依赖标准库包或者为了深入理解底层机制，我们需要手动实现这个功能。
Arrays.copyOfRange(original, from, to) 的行为是复制从 from 索引（包含）到 to 索引（不包含）的元素。我们可以通过一个简单的循环来实现同样的功能：
立即学习“Java免费学习笔记（深入）”；
/** * 手动实现数组分片功能，类似于 Arrays.copyOfRange。 * 创建一个新数组，包含 original 数组从 from 索引到 to 索引（不包含 to）的元素。 * * @param original 原始数组 * @param from 起始索引（包含） * @param to 结束索引（不包含） * @return 包含指定范围元素的新数组 */private static int[] copyArray(int[] original, int from, int to) { // 新数组的长度为 to - from int[] res = new int[to - from]; // 遍历原始数组的指定范围，并复制到新数组中 for (int i = from; i < to; i++) { res[i - from] = original[i]; } return res;}
有了 copyArray 方法，我们就可以在 mergeSort 函数中替换 Arrays.copyOfRange：
闪念贝壳
闪念贝壳是一款AI 驱动的智能语音笔记，随时随地用语音记录你的每一个想法。
218 查看详情 
/** * 递归实现归并排序。 * * @param A 待排序的数组 */static void mergeSort(int[] A) { // 基本情况：如果数组长度小于等于1，则认为它已经有序，无需进一步排序 if (A.length > 1) { int mid = A.length / 2; // 计算数组的中间索引 // 使用手动实现的 copyArray 方法分割数组 int[] leftArray = copyArray(A, 0, mid); // 左半部分：从0到mid-1 int[] rightArray = copyArray(A, mid, A.length); // 右半部分：从mid到A.length-1 // 递归地对左右子数组进行排序 mergeSort(leftArray); mergeSort(rightArray); // 将排序好的左右子数组合并回原始数组 A merge(A, leftArray, rightArray); }}
2.2. 标准两路合并函数 (Merge)
merge 函数负责将两个已排序的子数组合并成一个大的有序数组。这个过程通过维护三个指针（一个指向目标数组，两个分别指向两个源子数组）来实现。
/** * 将两个已排序的子数组 l 和 r 合并到目标数组 a 中。 * * @param a 目标数组，用于存放合并后的结果 * @param l 左子数组（已排序） * @param r 右子数组（已排序） */static void merge(int[] a, int[] l, int[] r) { int i = 0, li = 0, ri = 0; // i: 目标数组指针, li: 左子数组指针, ri: 右子数组指针 // 当左右子数组都有元素时，比较它们当前指向的元素，将较小的放入目标数组 while (li < l.length && ri < r.length) { if (l[li] < r[ri]) { a[i++] = l[li++]; // 左子数组元素较小，放入目标数组，并移动相应指针 } else { a[i++] = r[ri++]; // 右子数组元素较小（或相等），放入目标数组，并移动相应指针 } } // 如果左子数组还有剩余元素，将其全部复制到目标数组 while (li < l.length) { a[i++] = l[li++]; } // 如果右子数组还有剩余元素，将其全部复制到目标数组 while (ri < r.length) { a[i++] = r[ri++]; }}
3. 多路合并：实现三路合并函数 (MergeArrays3)
除了标准的二路合并，有时我们可能需要合并多个（例如三个或更多）已排序的数组。三路合并的原理与二路合并类似，但需要同时比较三个数组的当前最小元素。
原始的三路合并尝试代码存在逻辑缺陷，例如比较条件不完善、指针使用不当以及对剩余元素的处理不足。一个健壮的三路合并函数应该在每一步都找到所有非空数组中最小的元素，并将其添加到结果数组中，然后移动相应数组的指针。当某个数组耗尽时，它就不再参与比较。
我们可以通过使用一个“哨兵值”（如 Integer.MAX_VALUE）来简化比较逻辑。当一个数组的指针超出其边界时，我们将其对应的当前值视为 Integer.MAX_VALUE，这样它就不会被选为最小元素，直到所有实际元素都被处理完毕。
/** * 将三个已排序的数组 a, b, c 合并成一个大的有序数组。 * * @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, k = 0, resPtr = 0; // i, j, k 分别为数组 a, b, c 的指针；resPtr 为结果数组指针 // 循环直到所有数组的元素都被处理完毕 while (i < a.length || j < b.length || k < 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 = (k < c.length) ? c[k] : Integer.MAX_VALUE; // 找到三个值中的最小值，并将其添加到结果数组中 if (valA <= valB && valA <= valC) { // 确保 valA 确实来自有效索引，避免在所有数组都耗尽时重复添加 MAX_VALUE if (i < a.length) { result[resPtr++] = a[i++]; } else { // 如果 valA 是 MAX_VALUE 且被选为最小，说明所有数组都已耗尽，可以提前退出 break; } } else if (valB <= valA && valB <= valC) { if (j < b.length) { result[resPtr++] = b[j++]; } else { break; } } else { // valC 是最小值 if (k < c.length) { result[resPtr++] = c[k++]; } else { break; } } } return result;}
4. 完整代码示例
将上述所有方法整合到一个完整的 Java 类中，包括一个 main 方法用于测试。
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;// import java.util.Arrays; // 根据要求，不使用 Arrays 包public class MergeSortWithManualCopy { public static void main(String[] args) throws IOException { BufferedReader R = new BufferedReader(new InputStreamReader(System.in)); System.out.print("请输入数组大小: ");
以上就是Java中递归实现归并排序与多路合并：无包依赖的数组操作实践的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/987844.html
微信扫一扫 
支付宝扫一扫 
