C语言如何合并两个有序数组？

问题定义

给定两个已经按升序排列的数组 arr1 和 arr2，将它们合并成一个新的数组 merged_arr，merged_arr 也必须是有序的。

假设：

• arr1 的大小为 m
• arr2 的大小为 n
• merged_arr 的大小为 m + n

使用额外空间（最直观）

这是最简单的方法，创建一个足够大的新数组，然后通过比较两个原数组的元素,将较小的元素依次放入新数组中。

算法思路：

1. 创建一个大小为 m + n 的新数组 merged_arr。
2. 初始化三个指针（或索引）：
   • i：指向 arr1 的当前元素（从0开始）。
   • j：指向 arr2 的当前元素（从0开始）。
   • k：指向 merged_arr 的当前位置（从0开始）。
3. 开始一个循环，只要 i 和 j 都没有超出各自数组的长度：
   • 比较 arr1[i] 和 arr2[j]。
   • arr1[i] 更小，则将其复制到 merged_arr[k]，i++ 和 k++。
   • 否则，将 arr2[j] 复制到 merged_arr[k]，j++ 和 k++。
4. 循环结束后，可能有一个数组还有剩余元素，因为原数组本身是有序的，所以直接将这些剩余元素全部复制到 merged_arr 的末尾即可。

C语言代码实现：

#include <stdio.h>
#include <stdlib.h> // 用于 malloc 和 free
// 合并两个有序数组的函数
int* mergeSortedArrays(int arr1[], int m, int arr2[], int n) {
    // 1. 为合并后的数组分配内存
    int* merged_arr = (int*)malloc((m + n) * sizeof(int));
    if (merged_arr == NULL) {
        printf("内存分配失败!\n");
        return NULL; // 内存分配失败，返回NULL
    }
    int i = 0; // arr1的索引
    int j = 0; // arr2的索引
    int k = 0; // merged_arr的索引
    // 2. 比较并合并两个数组
    while (i < m && j < n) {
        if (arr1[i] < arr2[j]) {
            merged_arr[k++] = arr1[i++];
        } else {
            merged_arr[k++] = arr2[j++];
        }
    }
    // 3. 处理arr1中剩余的元素
    while (i < m) {
        merged_arr[k++] = arr1[i++];
    }
    // 4. 处理arr2中剩余的元素
    while (j < n) {
        merged_arr[k++] = arr2[j++];
    }
    return merged_arr;
}
// 打印数组的辅助函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main() {
    int arr1[] = {1, 3, 5, 7, 9};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int arr2[] = {2, 4, 6, 8, 10, 12};
    int n = sizeof(arr2) / sizeof(arr2[0]);
    printf("数组1: ");
    printArray(arr1, m);
    printf("数组2: ");
    printArray(arr2, n);
    int* merged = mergeSortedArrays(arr1, m, arr2, n);
    if (merged != NULL) {
        printf("合并后的数组: ");
        printArray(merged, m + n);
        // 记得释放动态分配的内存
        free(merged);
    }
    return 0;
}

复杂度分析：

• 时间复杂度：O(m + n),我们只需要遍历两个数组各一次。
• 空间复杂度：O(m + n),我们创建了一个新的数组来存储结果。

原地合并（适用于一个数组足够大的情况）

这是一个进阶技巧，常用于面试题的变体，如果题目中告诉你，其中一个数组（arr1）有足够的空间来容纳另一个数组的所有元素（即 arr1 的实际容量 >= m + n），那么你可以进行原地合并,无需额外空间。

算法思路：

1. 从后往前合并：这是原地合并的关键，如果从前往后，arr1 的元素会被覆盖，但从后往前，由于合并后的数组是最大的，我们可以将较大的元素先放到 arr1 的末尾，而不会覆盖掉还未处理的 arr1 元素。
2. 初始化三个指针：
   • p1：指向 arr1 的最后一个有效元素（索引 m - 1）。
   • p2：指向 arr2 的最后一个元素（索引 n - 1）。
   • p：指向 arr1 的最后一个位置（索引 m + n - 1）,这是合并后数组的末尾。
3. 开始循环，只要 p1 和 p2 都没有越界（即 p1 >= 0 且 p2 >= 0）：
   • 比较 arr1[p1] 和 arr2[p2]。
   • 将较大的那个元素放到 arr1[p] 的位置。
   • 移动较大的那个元素的指针和 p 指针。
4. 循环结束后，arr2 还有剩余元素（即 p2 >= 0），说明这些元素比 arr1 的所有元素都小，需要将它们全部移动到 arr1 的前面。arr1 还有剩余，则它们已经在正确的位置,无需操作。

C语言代码实现：

#include <stdio.h>
// 假设 arr1 的容量至少为 m+n
void mergeInPlace(int arr1[], int m, int arr2[], int n) {
    int p1 = m - 1;      // arr1 的最后一个元素索引
    int p2 = n - 1;      // arr2 的最后一个元素索引
    int p = m + n - 1;   // 合并后数组的最后一个元素索引
    // 从后往前比较并填充
    while (p1 >= 0 && p2 >= 0) {
        if (arr1[p1] > arr2[p2]) {
            arr1[p--] = arr1[p1--];
        } else {
            arr1[p--] = arr2[p2--];
        }
    }
    // arr2 还有剩余元素，将它们复制到 arr1 的前面
    // 这个循环只在 arr2 的元素比 arr1 的所有元素都小时才执行
    while (p2 >= 0) {
        arr1[p--] = arr2[p2--];
    }
}
int main() {
    // 注意：arr1 的实际容量必须 >= m + n
    // 这里为了演示，我们故意开大一点
    int arr1[10] = {1, 3, 5, 7, 9}; // m=5, 容量至少为 5+4=9
    int m = 5;
    int arr2[] = {2, 4, 6, 8}; // n=4
    int n = 4;
    printf("合并前的 arr1: ");
    for (int i = 0; i < m + n; i++) { // 打印整个 arr1 的容量
        printf("%d ", arr1[i]);
    }
    printf("\n");
    printf("数组2: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr2[i]);
    }
    printf("\n");
    mergeInPlace(arr1, m, arr2, n);
    printf("合并后的 arr1: ");
    for (int i = 0; i < m + n; i++) {
        printf("%d ", arr1[i]);
    }
    printf("\n");
    return 0;
}

复杂度分析：

• 时间复杂度：O(m + n),同样需要遍历所有元素。
• 空间复杂度：O(1)，没有使用额外的存储空间,直接在原数组上操作。

总结与选择

对于日常学习和一般应用，方法一是最常用和最安全的选择，对于算法面试，方法二则更能体现你对指针和内存管理的理解。