package Solution;

 /**

  * 有两个排序的数字A1和A2，内存在A1的末尾有足够多的空余空间容纳A2.

  * 请实现一个函数，把A2中的所有数字插入到A1中并且所有的数字是排序的。

  * @author GL

  * 本题应该注意Java中不可变数组的性质,所以用创建新数组接受插入排序后的元素

  */

 public class No4InsertSortedArrays {

     public static void main(String[] args) {

         int[] array1={4,5,6,7,8,10};

         int[] array2={1,2,3,4,5};

         int[] temp=insertSortedArrays(array1,array2);

         for(int k=0;k<temp.length;k++){

             System.out.print(temp[k]);

         }

     }

     /*

      * 从头到尾比较两个数组中的数字，把较大的数字复制到新数组的合适位置。

      */

     public static int[] insertSortedArrays(int[] array2,int[] array1){

         if(array1==null||array2==null)

             return null;

         int i=array1.length-1;

         int j=array2.length-1;

         int n=array1.length+array2.length-1;

         int[] temp=new int[array1.length+array2.length];

         while(n>=0){

             if(i>=0&&j>=0){

                 if(array1[i]>array2[j]){

                     temp[n]=array1[i];

                     n--;

                     i--;

                 }else if(array1[i]<array2[j]){

                     temp[n]=array2[j];

                     n--;

                     j--;

                 }else if(array1[i]==array2[j]){

                     temp[n]=array2[j];

                     temp[n-1]=array1[i];

                     n=n-2;

                     i--;

                     j--;

                 }

             }else if(i>=0&&j<0){

                 temp[n--]=array1[i--];

             }else if(i<0&&j>=0){

                 temp[n--]=array2[j--];

             }

         }

         return temp;

     }

 }