Java 中高效合并排序两个数组76

在 Java 中，经常会遇到需要将两个有序数组合并成一个有序数组的情况。合并排序是一种高效且稳定的排序算法，可以有效地解决这个问题。本文将介绍如何使用 Java 代码实现合并排序算法，以合并两个有序数组。

算法详解

合并排序算法的工作原理如下：1. 递归分解：将数组分解成更小的子数组，直到每个子数组只有一个元素。
2. 合并相邻子数组：将相邻的两个有序子数组合并成一个有序数组。
3. 重复合并：继续合并相邻的已排序子数组，直到所有子数组合并成一个有序的最终数组。

Java 代码实现public static int[] mergeSortedArrays(int[] arr1, int[] arr2) {
// 检查数组是否为空
if (arr1 == null || == 0) {
return arr2;
}
if (arr2 == null || == 0) {
return arr1;
}
// 创建一个新的数组来保存合并后的结果
int[] mergedArray = new int[ + ];
// 指向两个数组的游标
int i = 0;
int j = 0;
int k = 0;
// 循环合并两个数组
while (i < && j < ) {
if (arr1[i] < arr2[j]) {
mergedArray[k++] = arr1[i++];
} else {
mergedArray[k++] = arr2[j++];
}
}
// 将剩余的元素添加到合并后的数组中
while (i < ) {
mergedArray[k++] = arr1[i++];
}
while (j < ) {
mergedArray[k++] = arr2[j++];
}
// 返回合并后的数组
return mergedArray;
}

复杂度分析

合并排序算法的时间复杂度为 O(n)，其中 n 是两个数组的总元素数。这是因为算法在合并相邻的已排序子数组时执行线性时间的操作。合并排序是一种稳定的排序算法，这意味着具有相同值的元素在合并后的数组中的顺序将与输入数组中的顺序相同。

示例

考虑两个有序数组 arr1 = [1, 3, 5] 和 arr2 = [2, 4, 6]。使用上面介绍的算法合并这两个数组，结果将是 [1, 2, 3, 4, 5, 6]，这是一个有序的合并数组。

合并排序算法是一种高效且通用的方法，用于将两个有序数组合并成一个有序数组。Java 代码实现简单而高效，可以处理各种规模的输入数组。该算法的时间复杂度为 O(n)，使其成为合并有序数组的理想选择。

2024-10-24

上一篇：Java 数据库修改指南：掌握更新、删除和插入操作

下一篇：一维数组在 Java 中的全面指南