蓝桥杯-练一练「排序」c++（归并排序）

题目描述
题目来源
给定一个长度为 N 的数组 A，请你先从小到大输出它的每个元素，再从大到小输出它的每个元素。

输入描述
第一行包含一个整数 N。

第二行包含 N 个整数，表示数组 AA 的元素。

输出描述
输出共两行，每行包含 N 个整数，表示答案。

输入输出样例
示例 1
输入

5
1 3 2 6 5

输出

1 2 3 5 6
6 5 3 2 1

运行限制
最大运行时间：1s
最大运行内存: 128M

此题用冒泡、选择、插入 排序都会超时，因为数据量为10的5次幂，对于时间复杂度n方的算法都会超时，故选用归并排序的算法，时间复杂度为n*logn;
且此题用java写归并算法也会超时；故采用c++去写这个算法，不过语言不重要，重要的是算法和编程思想；

#include 
using namespace std;
int a[1000000];
int temp[1000000];
//归并
void merge(int low,int mid,int high) {
	int i=low;//第一组数组的头
	int j=mid+1;//第二组数组的他
	int k=i;//作为临时数组temp的索引
	while(i<=mid&&j<=high) {
		if(a[i]<=a[j])
			temp[k++]=a[i++];
		else
			temp[k++]=a[j++];
	}
	//剩余的数
	while(i<=mid)
		temp[k++]=a[i++];
	while(j<=high)
		temp[k++]=a[j++];
	//将排好序的临时数组 赋给a
	for(int m=low; m<=high; m++)
		a[m]=temp[m];
}
//分组->排序
void sort(int low,int high) {
	if(low>=high)
		return;
	int mid=low+(high-low)/2;
	//分成两组
	sort(low,mid);
	sort(mid+1,high);
	//对这两个有序组进行排序
	merge(low,mid,high);
}

int main() {
	int n;
	cin>>n;
	for(int i=0; i>a[i];
	}
	sort(0,n-1);
	for(int i=0; i=0; i--)
		cout< 
java代码（提交超时） 
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
    static int[] a = new int[1000000];
    static int[] temp = new int[1000000];

    //归并
    static void merge(int low, int mid, int high) {
        int i = low;//头指针
        int j = mid + 1;//尾指针
        int k = i;//作为临时数组temp的索引
        while (i <= mid && j <= high) {
            if (a[i] <= a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }
        //剩余的数
        while (i <= mid)
            temp[k++] = a[i++];
        while (j <= high)
            temp[k++] = a[j++];
        //将临时数组排好的赋值给a
        for (int m = low; m <= high; m++)
            a[m] = temp[m];
    }

    //分开—>排序
    static void sort(int low, int high) {
        if (low >= high)//递归出口
            return;
        int mid = low + (high - low) / 2;
        //将数组分为两组
        //左边
        sort(low, mid);
        //右边
        sort(mid + 1, high);
        //将两个有序数组进行合并
        merge(low, mid, high);
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n = scan.nextInt();
        for (int i = 0; i < n; i++)
            a[i] = scan.nextInt();
        //通过归并排序对a数组进行排序
        sort(0, n - 1);
        for (int i = 0; i < n; i++)
            System.out.print(a[i] + " ");
        System.out.println();
        for (int i = n - 1; i >= 0; i--)
            System.out.print(a[i] + " ");
        scan.close();
    }
}