给出两个“非递减有序”的线性表数组，将它们合并成一个“非递减有序的“的线性表数组

给出两个“非递减有序”的线性表数组，将它们合并成一个“非递减有序的“的线性表数组

给出两个“非递减有序”的线性表数组，将它们合并成一个“非递减有序的“的线性表数组，

例如，将 arr1[] = { 1, 3, 4, 5}, arr2[] = {2, 4, 6, 8}，合并为arr3[] = {1, 2, 3, 4, 4, 5, 6, 8}。

// 合并两个有序的数组
#include <iostream>
using namespace std;// 将 1-1] 和 2-1] 合并至 1+n2-1] 中
void mergeArrays(int arr1[], int arr2[],int n1, int n2, int arr3[])
{int i = 0, j = 0, k = 0;// 同时遍历两个数组while (i < n1 && j < n2){// 每次比较结果较小的元素插入arr3if (arr1[i] < arr2[j])   arr3[k++] = arr1[i++];else    arr3[k++] = arr2[j++];}// 剩余的arr1或arr2元素再复制到arr3中while (i < n1)   arr3[k++] = arr1[i++];while (j < n2)   arr3[k++] = arr2[j++];
}// 测试代码
int main()
{int arr1[] = {1, 3, 5, 7};int n1 = sizeof(arr1) / sizeof(arr1[0]);int arr2[] = {2, 4, 6, 8};int n2 = sizeof(arr2) / sizeof(arr2[0]);int arr3[n1 + n2];mergeArrays(arr1, arr2, n1, n2, arr3);cout << "Array after merging" << endl;for (int i = 0; i < n1 + n2; i++)cout << arr3[i] << " ";return 0;
}

 创建一个arr3数组，大小为arr1和arr2的大小之和，同时遍历arr1和arr2，每次比较结果较小的元素插入arr3，剩余的arr1或arr2元素再复制到arr3中。时间复杂度为O（n1+n2）。