排序---归并排序

我觉得要能独立写出某一个算法，就一定要在写代码之前有思路。时间复杂度（o（nlog（n）））

思路： 选择数组的中间值，对起左右进行递归，其中合并两个有序的数组，最后将放到tr数组中排序好的数重新放置到原数组中。

#include<cstdio>
using namespace std;
int sr[5],tr[5];
void rMerge(int sr[],int tr[],int s,int m,int t)   //合并两个有序的数组
{
    int i=s,j=m+1,k=s;
    while(i<=m&&j<=t){
        if(sr[i]<sr[j]) tr[k++]=sr[i++];
        else tr[k++]=sr[j++];
    }
    while(i<=m) tr[k++]=sr[i++];  //如果有多余的数，就直接加入到里面即可
    while(j<=t) tr[k++]=sr[j++];
}

void copy(int sr[],int tr[],int s,int t)
{
    for(int i=s;i<=t;i++)
    {
        sr[i]=tr[i];
    }
}

void aSort(int sr[],int s,int t)
{
    if(s<t)
    {
        int m=(s+t)/2;
        aSort(sr,s,m); //对其左右分别排序
        aSort(sr,m+1,t);
        rMerge(sr,tr,s,m,t); //合并到tr数组
        copy(sr,tr,s,t); //将tr数组重新返回到sr数组中
    }
}

int main()
{
    for(int i=0;i<5;i++) scanf("%d",&sr[i]);
    aSort(sr,0,4);
    for(int i=0;i<5;i++) printf("%d ",tr[i]);
    printf("
");
}