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

在许多算法问题中，需要将已排序的两个数组合并成一个按顺序排列的新数组。下面是一个C++程序，可以演示如何完成这个任务。这个程序将使用“归并排序”算法来合并两个已排序的数组。

算法介绍

归并排序是一种分治算法，它的基本思想是将原问题分解为若干个子问题解决，然后将子问题的结果合并得到原问题的解。对于本题，可以将两个已排序数组的合并视为一个归并排序的过程。

实现步骤

1.定义要合并的两个数组

首先，我们需要定义两个已排序的数组，这里我们定义两个整型数组a和b。

int a[] = {1, 3, 5, 7};
int b[] = {2, 4, 6, 8};

2.确定要合并的区域范围

接下来，我们需要确定要合并的区域。对于a和b两个数组，我们需要合并的区域是从0到数组长度减1。

int len_a = sizeof(a) / sizeof(a[0]);
int len_b = sizeof(b) / sizeof(b[0]);
int start_a = 0;
int end_a = len_a - 1;
int start_b = 0;
int end_b = len_b - 1;

3.开始合并

归并排序的核心是合并过程，我们需要编写一个函数来完成合并操作。下面是这个函数的实现：

void merge(int arr[], int start, int mid, int end) {
    int num1 = mid - start + 1;
    int num2 = end - mid;

    int *left = new int[num1];
    int *right = new int[num2];

    for(int i = 0; i < num1; i++) {
        left[i] = arr[start + i];
    }

    for(int j = 0; j < num2; j++) {
        right[j] = arr[mid + 1 + j];
    }

    int i = 0;
    int j = 0;
    int k = start;
    while(i < num1 && j < num2) {
        if(left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }

    while(i < num1) {
        arr[k] = left[i];
        i++;
        k++;
    }

    while(j < num2) {
        arr[k] = right[j];
        j++;
        k++;
    }

    delete[] left;
    delete[] right;
}

这个函数使用了两个指针left和right来表示要合并的左右两个数组，然后开始将左右两个数组合并到一个新的数组中。在这个过程中，我们需要不断比较左右数组中的元素，并将较小的元素放到合并后的数组中。

4.编写主函数

接下来，我们需要编写主函数来控制整个程序的流程。主函数中，我们要完成以下步骤：

（1）创建一个新数组，用来保存合并后的结果。

（2）按照归并排序的思路，将要合并的数组不断分解，直到每个细分数组都只有一个元素。

（3）开始将每个细分数组按顺序合并成更大的数组。

请看下面的代码：

int *result = new int[len_a + len_b];

while(start_a <= end_a && start_b <= end_b) {
    if(a[start_a] <= b[start_b]) {
        result[start_a + start_b] = a[start_a];
        start_a++;
    } else{
        result[start_a + start_b] = b[start_b];
        start_b++;
    }
}

while(start_a <= end_a) {
    result[start_a + start_b] = a[start_a];
    start_a++;
}

while(start_b <= end_b) {
    result[start_a + start_b] = b[start_b];
    start_b++;
}

for(int i = 0; i < len_a + len_b; i++) {
    cout << result[i] << " ";
}

delete[] result;

在主函数中，我们首先创建了一个新的数组result，用来保存合并后的结果。然后，按照归并排序的思路，我们不断将要合并的数组细分为较小的数组，直到每个细分数组都只有一个元素。最后，我们开始将每个细分数组按顺序合并成更大的数组，最终获得了一个按顺序排列的新数组result。

代码演示

下面是完整的C++代码，它演示了如何合并两个已排序的数组：

#include <iostream>

using namespace std;

void merge(int arr[], int start, int mid, int end) {
    int num1 = mid - start + 1;
    int num2 = end - mid;

    int *left = new int[num1];
    int *right = new int[num2];

    for(int i = 0; i < num1; i++) {
        left[i] = arr[start + i];
    }

    for(int j = 0; j < num2; j++) {
        right[j] = arr[mid + 1 + j];
    }

    int i = 0;
    int j = 0;
    int k = start;
    while(i < num1 && j < num2) {
        if(left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }

    while(i < num1) {
        arr[k] = left[i];
        i++;
        k++;
    }

    while(j < num2) {
        arr[k] = right[j];
        j++;
        k++;
    }

    delete[] left;
    delete[] right;
}

int main() {
    int a[] = {1, 3, 5, 7};
    int b[] = {2, 4, 6, 8};

    int len_a = sizeof(a) / sizeof(a[0]);
    int len_b = sizeof(b) / sizeof(b[0]);
    int start_a = 0;
    int end_a = len_a - 1;
    int start_b = 0;
    int end_b = len_b - 1;

    int *result = new int[len_a + len_b];

    while(start_a <= end_a && start_b <= end_b) {
        if(a[start_a] <= b[start_b]) {
            result[start_a + start_b] = a[start_a];
            start_a++;
        } else{
            result[start_a + start_b] = b[start_b];
            start_b++;
        }
    }

    while(start_a <= end_a) {
        result[start_a + start_b] = a[start_a];
        start_a++;
    }

    while(start_b <= end_b) {
        result[start_a + start_b] = b[start_b];
        start_b++;
    }

    for(int i = 0; i < len_a + len_b; i++) {
        cout << result[i] << " ";
    }

    delete[] result;
}

以上代码的输出结果为：