java实现合并两个有序顺序线性表

在Java中，合并两个已排序的顺序线性表（通常是数组或链表）可以采用递归或者迭代的方式来实现。这里我们以数组为例，介绍一种简单的合并算法：

**方法一：迭代合并**

public class MergeSortedArrays {
    public int[] merge(int[] nums1, int m, int[] nums2, int n) {
        int[] merged = new int[m + n];
        int i = 0, j = 0, k = 0;

        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }

        // 如果其中一个数组还有剩余元素，直接复制过来
        while (i < m) {
            merged[k++] = nums1[i++];
        }
        while (j < n) {
            merged[k++] = nums2[j++];
        }

        return merged;
    }
}

在这个例子中，我们创建一个新的数组`merged`，然后比较两个输入数组`nums1`和`nums2`中的当前元素，将较小的添加到新数组，并移动对应的指针。

**方法二：递归合并**
递归的方式可能会稍显复杂一些，但也能清晰地表达出合并的过程：

public class MergeSortedArraysRecursive {
    public int[] merge(int[] nums1, int m, int[] nums2, int n) {
        if (m == 0) {
            return nums2;
        } else if (n == 0) {
            return nums1;
        } else if (nums1[m - 1] <= nums2[0]) {
            return merge(nums1, m - 1, nums2, n);
        } else {
            return merge(nums1, m, Arrays.copyOfRange(nums2, 1, n + 1), n - 1);
        }
    }
}

这个版本的`merge`函数通过不断比较并合并两个数组的首元素，直到其中一个数组遍历完。