Question

题目描述 已知数组a中有m个按升序排列的元素，数组b中有n个按降序排列的元素，

编程将a与b中的所有元素按降序存入数组c中。
输入

输入有两行，第一行首先是一个正整数m，然后是m个整数；第二行首先是一个正整数n，然后是n个整数，m,
n均小于等于1000000。

输出

输出合并后的m+n个整数，数据之间用空格隔开。输出占一行。

样例输入
4 1 3 5 7
3 6 4 2

样例输出
7 6 5 4 3 2 1

一边比大小一边代入第三个数组该怎么弄？

Answer 1

由于输入的两组数字都不是有序的

所以可以有三种方式供选择

第一种，边输入 边插入排序 代码相对简单 

第二种，分别输入 排序 再一起组合 空间复杂度高

第三种，整体输入 一并排序 这种效率最高

按第一种方式 代码如下

#include <stdio.h>
int a[2000000];
int main()
{
	int m, n;
	int i, j,t;
	scanf("%d", &m);
	for(i = 0; i < m; i ++)
	{
		scanf("%d", &t);
		for(j = i-1; j >= 0; j --)
		{
			if(a[j] >= t) break;
			a[j + 1] = a[j];
		}
		a[j + 1] = t;
	}
	
	scanf("%d", &n);
	for(i = m; i < m+n; i ++)
	{	
		scanf("%d", &t);
		for(j = i-1; j >= 0; j --)
		{
			if(a[j] >= t) break;
			a[j + 1] = a[j];
		}
		a[j + 1] = t;
	}
	for(i = 0; i < m+n-1; i ++)
		printf("%d ", a[i]);
	printf("%d\n", a[i]);
	return 0;
}

追问

题目要求说是将输入的两组数先分别存入两个数组在存入第三个数组，一组数组是升序，一组是降序，我之前试过将两个数组先存入在冒泡排序，耗时太大。。

追答

可以试试仿照我发的程序 进行插入 不过时间开销也不小
也可以试试先存入数组 然后快排

追问

这几步是什么意思呢?
for(j = i-1; j >= 0; j --)
{
if(a[j] >= t)
break;
a[j + 1] = a[j];
}
a[j + 1] = t;

追答

自后向前查找 找到应该插入的位置(a[j]比t小的位置 则t应该插在a[j+1]处) 该位置之后所有元素 向后移动一位

追问

知道了，谢谢了。。