利用递归实现

递归

从两个数组的尾部开始比较，如果A[m-1] <= B[n-1],那么将最大数B[n-1]赋值给A[m+n-1],然后n-1，重复。反之将A[m-1]赋值给A[m+n-1],然后m-1。递归结束的标志有俩，当A的数组遍历完了而B没有(m==0&&n!=0),此时将B剩下的值赋值给A的数组；标志2就是，当n为0的时候，包括两种情况，第一种标志的结束标志m == 0,n == 0，另一种就是A的数组还没有遍历完B数组已经遍历完了（m!=0,n==0）,这时候A数组是排序好的，不需要再遍历排序。

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
       if(m == 0&&n!=0)//A的数组遍历完了，B没有
       {
           A[n-1] = B[n-1]; //直接赋值
           merge(A,0,B,n-1);
       }
       else if(n==0) //两个标志
           return;
       else{
       if(A[m-1]<=B[n-1]){
           A[m+n-1] = B[n-1];
           merge(A,m,B,n-1);
       }
        else{
            A[m+n-1] = A[m-1];
            merge(A,m-1,B,n);
        }
       }
    }
}

递归的循环版

递归比较方便，但是时间复杂度比较高，拆分成循环

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
      int i = m+n-1;
      for(;i >=0;i--){
          if(m == 0)
          {
              A[i] = B[n-1];
              n--;
          }
          else if(n == 0){}
          else{
              if(A[m-1]<=B[n-1])
              {
                  A[i] = B[n-1];
                  n--;
              }
              else{
                  A[i] = A[m-1];
                  m--;
              }
          }
      }
    }
}