题目描述
题目来源
给定一个长度为 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++去写这个算法，不过语言不重要，重要的是算法和编程思想；
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++];elsetemp[k++]=a[j++];}//剩余的数while(i<=mid)temp[k++]=a[i++];while(j<=high)temp[k++]=a[j++];//将排好序的临时数组 赋给afor(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; iimport 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(); }}