小菜鸡代码

解题思路:
    归并排序的思想就是，无限的分治直到分得只剩一个元素。

注意事项:
    笔者的思路来自bilibili博主Doger哔哔的视频，如果看不懂的可以去看看改博主的视频，讲的挺好的，适合小白。网址链接:https://www.bilibili.com/video/BV1t44y1H7Vw?spm_id_from=333.337.search-card.all.click.

参考代码:

#include<stdio.h>

int div();

int add();

int main()

{

    int n,i;

    n=10;

    int a[n],b[n];  

    //定义两个数组，a数组用于开始的输入的值，b数组用于存放排好序的数组                      

    for(i=0;i<n;i++){

        scanf("%d",&a[i]);

    }

    div(a,n,b);

    //调用分治思想的函数

    //这里a是数组的首地址，n是数组的长度，b是排好序的数组的首地址

    for(i=0;i<n;i++){

        printf("%d ",b[i]);

    }

    return 0;

}

int div(int *a,int n,int *b)

{

    if(n==1){

        //这里如果我们分治分到只剩下一个单位，我们就无须再分，就直接把a指向的值赋给b就好了

        *b=*a;

        return 0;

    }else{

        int mid=n/2;

        int store[n];

        div(a,mid,store);    

        //参数分别对应分组1 的首地址，长度，储存首地址.

        div(a+mid,n-mid,store+mid);

        //对应分组2的首地址，长度，储存首地址

        add(store,mid,store+mid,n-mid,b);

        //把两个分组排序合并

    }

}

int add(int *a,int n,int *b,int m,int *c)

{

    int i=0,k=0,p=0;

    while(i!=n&&k!=m){

        if(a[i]<b[k]){

            c[p]=a[i];

            p++,i++;

        }else{

            c[p]=b[k];

            p++,k++;

        }

    }

    if(n==i&&m==k){

        return 0;

    }else if(n==i&&k!=m){

        while(m!=k){

            c[p]=b[k];

            p++,k++;

        }

    }else{

        while(n!=i&&k==m){

            c[p]=a[i];

            i++,p++;

        }

    }

}