两个有序数组合并

image.png

1.我用的归并

2.参考答案，直接插入

image.png

3. 看过答案思路写的

3.代码

#include <stdio.h>
void printArray(int a[], int n){
  for(int p = 0; p<n ; p++){
    printf("%d ",a[p]);
  } 
}

//方法一：数组移位
void test(int a[], m, n){
    int q =0;//记录前面已经正确的位置(不需要参与比较了)
    // 后数组  逐个找正确位置，找到位置数组后移插入
    for(int i=m;i<n ;i++){
        int temp = a[i];
        //前数组 该数组末尾随着插入 后移
        for(int j=q; j < i;j++){
            if( a[j] > temp ){
                //向后移动数组，将a[i]插入j的位置
                for(int s=i-1;s>=j;s--){
                    a[s+1] = a[s];
                }
                a[j]=temp;  
                q++;
                break;
            }
       }
    }
 printArray(a,n);
}
//方法二：方法一的优化
void test2(int a[], int m, int n){
    int i,j;
    int temp;
    //后数组  遍历
    for(i = m; i<n; ++i){
        temp = a[i];
        //逐个后移 元素，直到找到合适的位置
        /*
        *将移位和查找合适位置结合了,方法一查到位置后还得移动位置
        *这里直接通过移动位置一个一个查找合适的位置
        */
        for(j=i-1; j>=0 && temp<a[j];--j)
            a[j+1]=a[j];
        a[j+1] = temp;
    }
  printArray(a,n);
}

//方法三：归并，效率最高，但是申请了额外空间
void test3(int a[], m, n){
    int temp[n];//申请了空间
    int i = 0;
    int j= m;
    int q =0;
    while(i<m && j<n){
        if(a[i]>a[j]){
            temp[q++]=a[j++];
        }else{
         temp[q++]=a[i++];
        }
    }
    while(i<m){
      temp[q++]= a[i++];
    }
    
    while(j<n){
      temp[q++]= a[j++];
    }
  printArray(a,n);   
}

int main()
{
    int a[]={5,6,7,8,4,5,6};
    test2(a, 4,7);
}