将两个已排好序数组合并成一个排好序数组_有2个顺序排列好的整数数组array1、array2,编写程序合并这两个数组为一个排序排列

主函数：

定义两个随机数组 分别排序 排序后合并 再排序 再输出

int main() {
	int *x, m = 10, i, *y, *z, n = 20;
	x = random(m, 100);
	y = random(n, 100);
	sort(x, m);
	sort(y, n);
	output_array(x, m);
	output_array(y, n);
	z = merge(x, y, m, n);
	output_array(z, m + n);
	delete[]x;
	delete[]y;
	delete[]z;
}

产生随机数的函数 

int *random(int n, int max) {
	int *p = new int[n];
 
	for (int i = 0; i < n; i++) {
		p[i] = rand() % (max + 1);
		//cout << p[i] << " "  ;
	}
 
	return p;
}

p[i]:可以这么用，数组就相当于指针；

return p;返回指针，可以用此方法返回整个数组的内容。相比全局变量更好。

        动态内存分配：

临时分配一片内存空间用于存放数据。

方法一：

int *p;
p=new int;
*p=5;

方法二：

int *p = new int[n];

用new动态分配的空间必须要delete释放：方法一：delete p; 方法二: delete [] p;

冒泡法

void sort(int a[], int n) {
	//冒泡法
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - 1 - i; j++) {
			if (a[j] >= a[j + 1]) {
				int t = a[j];
				a[j] = a[j + 1];
				a[j + 1] = t;
			}
		}
	}
}

 传入参数为 数组 数组中元素个数；排序

输出数组

void output_array(int a[], int n) {
	for (int i = 0; i < n; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}

合并数组

传入参数 两个数组 以及他们的个数

分配空间为m+n大小（merge函数中将两个已排好序数组合并成一个排好序数组，重新采用排序算法并不是一个好的方法，因为效率较低。想想两个已经按身高排好队的队伍合并到一起的时候采用什么方法）

两个数组已经排好序 首先比较数组AB的第一个元素，将小的元素按顺序放入新数组C，再将刚得到的较大数与另一个数组的第二个元素比较。。。。

m、n 两列数的个数

num_m,num_n：分别遍历两个数列所需的下标参数。

比较：两列数组中，各取一个数比较，较小的那个放入新数组。放入后，其下标参数加1，指向下一个比他大的同数组的数，与刚才那个较大的数比较，再将较小的数传入新数组。

一个数组中的数全部传入新数组了，那么另一个数组的数无需排序，直接放入。

int *merge(int x[], int y[], int m, int n) {
	int *p = new int[m + n ];
	int num_x = 0, num_y = 0, temp = 0;
	while (num_x < m && num_y < n) {
		if (x[num_x] <= y[num_y]) {
			p[temp] = x[num_x];
			num_x++;
		} else {
			p[temp] = y[num_y];
			num_y++;
		}
		temp++;
	}
	while (num_x < m) {
		p[temp] = x[num_x];
		temp++;
		num_x++;
	}
	while (num_y < n) {
		p[temp] = y[num_y];
		temp++;
		num_y++;
	}
	return p;
}

num_x表示比较到x数组的几号元素  num_y表示比较到y数组的几号元素

当两个都没有比较完时，如果x的元素小于y的元素，就将x的元素存储。y的元素和x的下一个元素比较，如果y的元素小于x的下一个元素，就将y的元素存储，再有x的下一个元素和y的下一个元素比较；如果y的元素大于x的下一个元素，就将x的下一个元素存储，再有x的下下一个元素和y的元素比较。以此类推。

如果有一项数组的元素全部都排序到了新数组中，说明第二个数组中所有元素都大于他，且排序好了，直接加入就可以。