C++ 合并两个未排序数组的程序

在本文中，我们将编写一个程序来合并两个未排序数组。输出将是按升序排列的已排序数组。

输入： a[] = {10, 5, 15}

b[] = {20, 3, 2}

输出： 合并后按排序顺序排列的数组 {2, 3, 5, 10, 15, 20}

输入： a[] = {1, 10, 5, 15}

b[] = {20, 0, 2}

输出： 合并后按排序顺序排列的数组 {0, 1, 2, 5, 10, 15, 20}

方法 1

这里可以使用的方法是将两个数组连接起来，然后对连接后的数组进行排序。我们创建一个大小等于前两个数组总和的第三个数组，然后将两个数组的所有元素都传输到结果数组中。在追加操作之后，我们对结果数组进行排序。

C 代码

输出

The sorted array is:  1 2 3 5 7 10 12 15 20 22 100

时间复杂度

O((n+m)log(n+m)，其中 n 和 m 是数组的大小

空间复杂度

O(n+m)

方法 2

当使用先排序再合并到第三个数组的想法时，上述方法可以得到优化。分别对两个数组进行排序，然后将它们合并到结果数组中。

C 代码

输出

The sorted array is:  1 2 3 5 7 10 12 15 20 22 100

时间复杂度

O (nlogn + mlogm + (n + m)) // 这比方法 1 好得多

空间复杂度

O ( (n + m) ) 与方法 1 相同