输入两个有序数组合并

将两个有序数组合并的方法有两种。第一种方法是将第二个数组的元素全部插入到第一个数组的尾部，然后对合并后的第一个数组进行排序。这种方法的时间复杂度是O((n+m)log(n+m))，其中n是第一个数组的长度，m是第二个数组的长度。第二种方法是使用双指针法，分别从两个数组的开头开始比较元素大小，并逐个将较小的元素插入到一个新的数组中。这种方法的时间复杂度是O(n+m)，其中n是第一个数组的长度，m是第二个数组的长度。您可以根据具体情况选择合适的方法来合并两个有序数组。

相关问题

两个递增有序的数组合并用C语言做

同样可以使用归并排序的思想来合并两个递增有序的数组。具体步骤如下：

1. 定义两个指针i和j，分别指向两个数组的起始位置；
2. 定义一个新的数组result，用于存放合并后的结果；
3. 比较数组1和数组2中i和j位置上的元素大小，将较小的元素添加到result数组中，并将指针i或j向后移动一位；
4. 重复步骤3，直到任意一个数组的元素全部添加到result数组中；
5. 将另一个数组中剩余的元素添加到result数组中；
6. 返回result数组。

以下是C语言实现代码：

#include <stdio.h>

int* merge_sorted_arrays(int arr1[], int arr2[], int m, int n) {
    int i = 0, j = 0, k = 0;
    int* result = (int*)malloc((m + n) * sizeof(int));

    while (i < m && j < n) {
        if (arr1[i] <= arr2[j]) {
            result[k] = arr1[i];
            i++;
        } else {
            result[k] = arr2[j];
            j++;
        }
        k++;
    }

    while (i < m) {
        result[k] = arr1[i];
        i++;
        k++;
    }

    while (j < n) {
        result[k] = arr2[j];
        j++;
        k++;
    }

    return result;
}

int main() {
    int arr1[] = {1, 3, 5, 7, 9};
    int arr2[] = {2, 4, 6, 8, 10};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    int* result = merge_sorted_arrays(arr1, arr2, m, n);

    for (int i = 0; i < m + n; i++) {
        printf("%d ", result[i]);
    }

    free(result);
    return 0;
}

注意，以上实现假设两个输入数组已经是递增有序的。如果不是，则需要在合并前先对它们进行排序。另外，需要记得在函数结束时释放动态分配的数组空间，避免内存泄漏。

两个递增有序的数组合并另一个数组用C语言做

如果要合并3个或多个递增有序的数组，可以使用归并排序的思想。具体步骤如下：

1. 定义一个新的数组result，用于存放合并后的结果；
2. 将第一个数组和第二个数组合并成一个新的数组temp，即调用前面已经实现的合并两个有序数组的函数merge_sorted_arrays()；
3. 将temp数组和第三个数组合并成一个新的数组temp2，即再次调用merge_sorted_arrays()函数，将合并后的结果存放到temp2中；
4. 重复步骤3，直到所有数组都被合并到temp2中；
5. 将temp2数组中的元素拷贝到result数组中；
6. 返回result数组。

以下是C语言实现代码：

#include <stdio.h>

int* merge_sorted_arrays(int arr1[], int arr2[], int m, int n) {
    int i = 0, j = 0, k = 0;
    int* result = (int*)malloc((m + n) * sizeof(int));

    while (i < m && j < n) {
        if (arr1[i] <= arr2[j]) {
            result[k] = arr1[i];
            i++;
        } else {
            result[k] = arr2[j];
            j++;
        }
        k++;
    }

    while (i < m) {
        result[k] = arr1[i];
        i++;
        k++;
    }

    while (j < n) {
        result[k] = arr2[j];
        j++;
        k++;
    }

    return result;
}

int* merge_sorted_arrays_multiple(int* arrays[], int n, int lengths[]) {
    int* temp = NULL;
    int temp_length = 0;

    for (int i = 0; i < n; i++) {
        temp = merge_sorted_arrays(temp, arrays[i], temp_length, lengths[i]);
        temp_length += lengths[i];
    }

    int* result = (int*)malloc(temp_length * sizeof(int));
    memcpy(result, temp, temp_length * sizeof(int));
    free(temp);
    return result;
}

int main() {
    int arr1[] = {1, 3, 5, 7, 9};
    int arr2[] = {2, 4, 6, 8, 10};
    int arr3[] = {11, 13, 15, 17, 19};
    int* arrays[] = {arr1, arr2, arr3};
    int lengths[] = {5, 5, 5};
    int n = sizeof(arrays) / sizeof(arrays[0]);
    int* result = merge_sorted_arrays_multiple(arrays, n, lengths);

    for (int i = 0; i < n * 5; i++) {
        printf("%d ", result[i]);
    }

    free(result);
    return 0;
}

注意，以上实现假设所有输入数组已经是递增有序的。如果不是，则需要在合并前先对它们进行排序。另外，需要记得在函数结束时释放动态分配的数组空间，避免内存泄漏。