剑指offer面试题4拓展——已排序数组的合并

题目：有两个排序的数组A1和A2,内存在A1的末尾有足够的空间来容纳数组A2,请实现一种函数，把A2的所有数字插入到A1中并且所有的数字是排序的

//思路：设置两个索引indexofA1,indexofA2分别指向数组A1和A2的最后一个元素，即两个数组的尾部；
//比较两个索引指向的元素的大小:若indexofA1指向的元素（即A1[indexofA1])大于indexofA2指向的元素(即A2[indexofA2])，则将indexofA1指向的元素拷贝到临时数组Temp中（Temp从后往前拷贝）,然后indexofA1向前移动一个位置，然后再将indexA1指向的元素与indexofA2指向的元素进行比较；若indexofA1指向的元素小于indexofA2所指向的元素，则将indexofA2指向的元素拷贝到临时数组，indexofA2--,然后再将indexA2指向的元素与indexofA1指向的元素进行比较；若indexofA1指向的元素和indexofA2指向的元素相等，则将这两个元素都拷贝到数组Temp中，然后indexofA1--,indexofA2--；以此类推，直到数组A1和A2的元素全部拷贝到数组Temp中， 最后将数组Temp中的全部元素依次复制数组A1中。这里用到了辅助内存temp[]

代码

//有两个排序的数组A1和A2,内存在A1的末尾有足够的空间来容纳数组A2,请实现一种函数，把A2的所有数字插入到A1中并且所有的数字是排序的

//思路：设置两个索引indexofA1,indexofA2分别指向数组A1和A2的最后一个元素，即两个数组的尾部；
//比较两个索引指向的元素的大小:若indexofA1指向的元素（即A1[indexofA1])大于indexofA2指向的元素(即A2[indexofA2])，
//                                 则将indexofA1指向的元素拷贝到临时数组Temp中,然后indexofA1向前移动一个位置，然后再将indexA1指向的元素与indexofA1指向的元素进行比较
//
//                             若indexofA1指向的元素小于indexofA2所指向的元素，则将index
//
#include<iostream>
using namespace std;
#define A1length 4
#define A2length 5
void Array_Merge(int A1[],int n1,int A2[],int n2)//n1,n1分别为数组A1和A2中实际元素的数目
{
	if(A1==NULL || A2==NULL || n1<=0 ||n2<=0)
	{
		cout<<"invalid parameter!"<<endl;
		return ;
	}
	int totallength=n1+n2-1;
	int indexofA1=n1-1;
	int indexofA2=n2-1;
	int *Temp=(int *)malloc(sizeof(int)*(n1+n2));
	if(Temp==NULL)
	{
		cout<<"insufficient memory!"<<endl;
		return;
	}
	while(indexofA1>=0 && indexofA2>=0 )//
	{
		if(A2[indexofA2]>A1[indexofA1])
		{
			Temp[totallength--]=A2[indexofA2];
			indexofA2--;
		}
		else if(A2[indexofA2]<A1[indexofA1])
		{
			Temp[totallength--]=A1[indexofA1];
			indexofA1--;
		}
		else
		{
			Temp[totallength--]=A1[indexofA1];
			Temp[totallength--]=A2[indexofA2];
			indexofA1--;
			indexofA2--;
		}
	}
	while(indexofA2>=0)//考虑A1的索引indexofA1先变为-1，此时A1的元素已经全部拷贝到数组Temp中，
		               //此后只需将A2的剩余元素依次拷贝到数组Temp中；
	{
		Temp[totallength--]=A2[indexofA2];
		indexofA2--;
	}
	//cout<<"indexofA2:"<<indexofA2+1<<endl;
	while(indexofA1>=0)//考虑A2的索引indexofA2先变为-1，此时A2的元素已经全部拷贝到数组Temp中，
		               //此后只需将A1的剩余元素依次拷贝到数组Temp中；
	{
		Temp[totallength--]=A1[indexofA1];
		indexofA1--;
	}
	//cout<<"indexofA1:"<<indexofA1+1<<endl;
	for(int i=0;i<=n1+n2-1;i++)
	{
		A1[i]=Temp[i];
	}
}
int main(void)
{
	int A1[10];
	int A2[5];
	int i;
	cout<<"input the array A1:"<<endl;
	for(i=0;i<A1length;i++)
		cin>>A1[i];
	cout<<"input the array A2:"<<endl;
	for(i=0;i<A2length;i++)
		cin>>A2[i];
    Array_Merge(A1,A1length, A2,A2length);
	for(i=0;i<A1length+A2length;i++)
	{
		cout<<A1[i]<<" ";
	}
	cout<<endl;
	return 0;
}