问题 A: 二路归并排序(mergesort)递归法 [2*+]

问题 A: 二路归并排序(mergesort)递归法 [2*+]

时间限制: 1 Sec  内存限制: 128 MB
提交: 174  解决: 0
[提交][状态][讨论版][命题人:外部导入]

题目描述

二路归并排序(mergesort)递归法
用递归法进行二路归并排序
输入：第一行一个数据n，表示有n个数要排序。接下来n行每行一个<=10^7的整数。
输出：n行，由小到大排序后的数据
数据规模：n<=10^5
思考：两个递归都会被执行吗？

简单归并排序。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <iomanip>
using namespace std;
int a[100005];
//后台测试样例出错，答案正确显示运行错误20%
void Merge(int l1,int r1,int l2,int r2,int a[])
{
    int i=l1,j=l2;
    int t=0;
    int x[100005];
    while(i<=r1&&j<=r2)
    {
        if(a[i]<=a[j])
        {
            x[t++]=a[i++];
        }
        else
            x[t++]=a[j++];
    }
    while(i<=r1)
        x[t++]=a[i++];
    while(j<=r2)
        x[t++]=a[j++];
    for(int m=0;m<t;m++)
    {
        a[m+l1]=x[m];
    }
}
void mergesort(int left,int right,int a[])
{
    if(left<right)
    {
        int pos=(left+right)/2;
    mergesort(left,pos,a);
    mergesort(pos+1,right,a);
    Merge(left,pos,pos+1,right,a);
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    mergesort(0,n-1,a);
    for(int i=0;i<=n-1;i++)
    {
        cout<<a[i]<<endl;
    }
    return 0;
}