C语言 合并两个有序数组

#include "head.h"
 
int* mergeTwoSeqArr(int* a,int la,int* b,int lb){
    int i = 0,j=0;
    int *stack = (int*)malloc(sizeof(int)*(la+lb));
    int top = 0;
    while(i<la&&j<lb){
        if(a[i]<=b[j]){
            stack[top++] = a[i++];
        }else {
            stack[top++] = b[j++];
        }
    }
    while(i<la){
        stack[top++] = a[i++];
    }
    while(j<lb){
        stack[top++] = b[j++];
    }
    return stack;
}
 
 
int main(){
    int min = 1,max = 100,la = 10,lb = 20;
    int* arr1 = getAscendArr(min,max,la);
    int* arr2 = getAscendArr(min,max,lb);
    int* r = NULL;
    displayArr(arr1,la);
    displayArr(arr2,lb);
    r = mergeTwoSeqArr(arr1,la,arr2,lb);
    displayArr(r,la+lb);
    return 0;
}

合并两个有序数组的算法原理是使用归并排序的思想。

1、首先，我们创建一个新的数组来存储合并后的结果，长度为两个输入数组长度的总和。

2、设置三个指针 i、j 和 k，分别指向第一个数组、第二个数组和合并后数组的当前位置。

3、比较两个输入数组的当前元素，将较小的元素放入合并后的数组，并移动对应的指针：

如果 arr1[i] <= arr2[j]，将 arr1[i] 放入合并后的数组，并移动指针 i 和 k。

如果 arr1[i] > arr2[j]，将 arr2[j] 放入合并后的数组，并移动指针 j 和 k。

4、重复步骤 3，直到其中一个输入数组的所有元素都被合并。

5、将剩余的元素从另一个未完成遍历完的输入数组中放入合并后的数组。

6、返回合并后的数组。

这种算法的时间复杂度为 O(n1 + n2)，其中 n1 和 n2 分别为两个输入数组的长度。因为我们需要遍历两个数组来比较和合并元素，所以时间复杂度与两个数组的总长度成正比。

在上面的示例代码中，通过循环和逐个比较元素的方式实现了这个算法。