首页 计算机学科 java 编程题

# 合并两个有序数组 - 改动

将数组内两个区间内的有序元素合并

[1, 5, 6, 2, 4, 10, 11]

可以视作两个有序区间

[1, 5, 6] 和 [2, 4, 10, 11]

合并后，结果扔存储于原有空间

[1, 2, 4, 5, 6, 10, 11]

a1 原始数组，a2 结果数组 (k)

i, iEnd 第一个有序区间的起点和终点，j，jEnd 第二个有序区间的起点和终点

merge([1, 5, 6], [2, 4, 10, 11], a2 = [])
{
   merge([5, 6], [2, 4, 10, 11], a2 = [1])
	{
   	merge([5, 6], [4, 10, 11], a2 = [1, 2])
		{
      	merge([5, 6], [10, 11], a2 = [1, 2, 4])
			{
         	 merge([6], [10, 11], a2 = [1, 2, 4, 5])
				{
            	 merge([], [10, 11], a2 = [1, 2, 4, 5, 6])
					{
               	 merge([], [], a2 = [1, 2, 4, 5, 10, 11])
						{
						}
					}
				}
			}
		}
	}
}

代码：

public static void main(String[] args)
    {
        int arr[] = {1, 5, 6, 2, 4, 10, 11};
        // 保存所有合并后的结果的数组
        int arr1[] = new int[arr.length];
        merge(arr, 0, 2, 3, 6, arr1, 0);
        System.out.println(Arrays.toString(arr1));
    }
    public static void merge(int a1[], int i, int iEnd, int j, int jEnd, int a2[], int k)
    {
        // 判断如果 a1 数组中的左边区域没有可以比较的元素了就将剩余的元素拷贝到 a2 中
        if(i > iEnd)
        {
            System.arraycopy(a1, j, a2, k, jEnd - j + 1);
            return;
        }
        // 判断如果 a1 数组中的右边区域没有可以比较的元素了就将剩余元素拷贝到 a2 中
        if(j > jEnd)
        {
            System.arraycopy(a1, i, a2, k, iEnd - i + 1);
            return;
        }
        // 判断 a1 的 左边区域的 元素 与 右边区域的元素 大小
        if(a1[i] < a1[j])
        {
            // 将左边区域的元素赋值到 a2 的 k 位置
            a2[k] = a1[i];
            // 递归 i 后移 k 后移
            merge(a1, i + 1, iEnd, j, jEnd, a2, k + 1);
        }else
        {
            // 将右边区域的元素赋值到 a2 的 k 位置
            a2[k] = a1[j];
            // 递归 j 后移 k 后移
            merge(a1, i, iEnd, j + 1, jEnd, a2, k + 1);
        }
    }
# 非递归方式
思路分析：
i
1 5 6

j
2 4 10 11

刚开始，1 比 2 小所以将 1 赋值到 a2 中去
k
1

赋值完后 i 进行 + 1，k 也 + 1
	i
1	5	6

	k
1

进行下一轮比较 2 跟 5 比较 j 小 。将 2 赋值到 a2 的 k 位置中 ，然后 j + 1 ，然后 k + 1
	k
1	2

	j
2	4	10	 11

		k
1	2

接着下一轮 5 跟 4 比较 4 小，赋值到 a2 的 k 位置中，然后 j + 1，然后 k + 1
		k
1	2	4

		j
2	4	10	 11

			k
1	2	4

接着下一轮 5 跟 10 比较 5 小 ，赋值到 a2 的 k 位置中，然后 i + 1，然后 k + 1
			k
1	2	4	5

		i
1	5	6

				k
1	2	4	5

接着下一轮 6 跟 10 比较 6 小，赋值到 a2 的 k 位置中，然后 i + 1，然后 k + 1
				k
1	2	4	5	6

			i
1	5	6

					k
1	2	4	5	6

此时 i 超过它的边界了 ，我们可以设定一个条件当 i 大于 iEnd 后就把 j 剩余的部分都拷贝到 a2 数组中
代码：
public static void main(String[] args)
    {
        int arr[] = {1, 5, 6, 2, 4, 10, 11};
        // 保存所有合并后的结果的数组
        int arr1[] = new int[arr.length];
        merge1(arr, 0, 2, 3, 6, arr1);
        System.out.println(Arrays.toString(arr1));
    }
    public static void merge1(int a1[], int i, int iEnd, int j, int jEnd, int a2[])
    {
        int k = 0;
        while(i <= iEnd && j <= jEnd)
        {
            if(a1[i] < a1[j])
            {
                a2[k] = a1[i];
                i++;
            }else
            {
                a2[k] = a1[j];
                j++;
            }
            k++;
        }
        if(i > iEnd)
        {
            System.arraycopy(a1, j, a2, k, jEnd - j + 1);
        }
        if(j > jEnd)
        {
            System.arraycopy(a1, i, a2, k, iEnd - i + 1);
        }
    }