1 void merge(int A[], int m, int B[], int n) { 2 int *a=A,*b=B; 3 int i=0,j=0; 4 if(n==0||m==0){ //针对特殊情况,比如A或B中无元素的情况 5 if(n==0&&m!=0||n==0&&m==0) 6 return; 7 else 8 for(i=0;i<n;i++) 9 A[i]=B[i]; 10 return; 11 } 12 do{ 13 while(*b>=*a&&i<m){ 14 a++; 15 i++; // i记录A中要插入的位置 16 } 17 for(j=m;j>i;j--) //A中从第i个开始往后移动一位 18 A[j]=A[j-1]; 19 *a=*b; 20 m++; //每循环一次,A中元素增加一个 21 b++; //b指针往后取元素 22 n--; 23 a++; //a指针也往后移一位,指向刚插进去的元素的后一个元素 24 i++; 25 }while(n>0); 26 return; 27 }
题意:将两个有序的数组(升序)合并为一个有序的数组(升序),将合并后的数组存储在A中。
注意:要考虑数组A或B中可能没有元素的情况。以数组作为实参传给形参传的是地址,所以在这个函数中操作数组A和B是直接对数组的直接操作,而m和n就只是盏中的一个实参副本,可随便改。
思路:把B中的元素从小到大逐个取出来,插入到A中去,要将合适位置后面的所有元素往后移一位。几乎每插一个进A都要移动A中的元素,除非特殊情况,如B中的最小元素比A中的最大元素要大,那么就不需要移动了。这个算法的效率还是不怎样的,应该有更好的算法,只是这个挺简洁的了。