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代码

#include 
using namespace std;

void sortedMerge(int a[], int b[], int res[],
    int n, int m) // Merge two arrays in unsorted manner
{
    // Concatenate two arrays
    int i = 0, j = 0, k = 0;
    while (i < n) { // iterate in first array
        res[k] = a[i]; // put each element in res array
        i += 1;
        k += 1;
    }
    while (j < m) { // iterate in the second array
        res[k] = b[j]; // put each element in res array
        j += 1;
        k += 1;
    }

    sort(res, res + n + m); // sort the res array to get the sorted Concatenate
}

int main()
{
    int a[] = { 10, 5, 15, 22, 100 };
    int b[] = { 20, 3, 2, 12, 1, 7 };
    int n = sizeof(a) / sizeof(a[0]); // find the size of array a
    int m = sizeof(b) / sizeof(b[0]); // find the size of array b

    int res[n + m]; // create res array to Concatenate both the array
    sortedMerge(a, b, res, n, m); // call function to append and sort

    cout << "The sorted array is: ";
    for (int i = 0; i < n + m; i++)
        cout << " " << res[i];
    cout << "\n";

    return 0;
}

输出

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代码

// CPP program to merge two unsorted lists
// in sorted order
#include 
using namespace std;
void sortedMerge(int a[], int b[], int res[],
    int n, int m) // Merge two arrays in unsorted manner

{
    sort(a, a + n); // Sort the array a 
    sort(b, b + m); // sort the array b 


    int i = 0, j = 0, k = 0;
    while (i < n && j < m) { // After the array are sorted compare and merge to third array 
        if (a[i] <= b[j]) { // if element of a is less than b 
            res[k] = a[i]; // put element of a into the res and increment i 
            i += 1;
            k += 1;
        } else {
            res[k] = b[j]; // otherwise put the element  of b into the  res array and increment j
            j += 1;
            k += 1;
        }
    }
    while (i < n) { // If array a elements are left in the array put in res
        res[k] = a[i];
        i += 1;
        k += 1;
    }
    while (j < m) { // If array a elements are left in the array put in res
        res[k] = b[j];
        j += 1;
        k += 1;
    }
}

int main()
{
    int a[] = { 10, 5, 15, 22, 100 };
    int b[] = { 20, 3, 2, 12, 1, 7 };
    int n = sizeof(a) / sizeof(a[0]); // find the size of array a
    int m = sizeof(b) / sizeof(b[0]); // find the size of array b

    int res[n + m]; // create res array to Concatenate both the array
    sortedMerge(a, b, res, n, m); // call function to append and sort

    cout << "The sorted array is: ";
    for (int i = 0; i < n + m; i++)
        cout << " " << res[i];
    cout << "\n";

    return 0;
}

输出

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相同