有序数组合并算法的实现思路和方法是啥

归并算法之有序数组合并算法实现

一个简单的有序数组合并算法：写一个函数，传入 2 个有序的整数数组，返回一个有序的整数数组。实现相当简单，创建一个长度为这两个长度之和的数组，然后分别用三个指针指向这三个数组，找到这两个数组中各个元素在合并数组中的位置并插入，直到某个数组指针到达尾部。再将另一个数组剩下的所有元素，直接放入归并数组尾部。算法的简单实现，需要注意的是对参数的校验，判断数组是否有序。

public class MergeOrderedArray {
 
 public static int[] merge(int [] a,int []b){
 
  if(!isOrderedArray(a)){
     
   System.out.println(" array a is not an ordered array.");
     
   return null;
 
  }
 
    
  if(!isOrderedArray(b)){
     
   System.out.println(" array b is not an ordered array.");
     
   return null;
 
  }
     
   
  int a_len = a.length;
     
  int b_len = b.length;
     
  int[] merge = new int[a_len+b_len];
     
  int i=0,j=0,k=0;
     
  while(ia_len&
    &
jb_len){
 
   if(a[i]b[j]){
     
    merge[k++]=a[i++];
 
   }
else{
     
    merge[k++]=b[j++];
 
   }
 
  }
 
   
  //A数组全部合并完毕，将b数组剩余直接加入合并数组 
  if(i==a_len){
     
   for(;
    jb_len;
j++){
     
    merge[k++]= b[j];
 
   }
 
  }
else{
     
   for(;
    ia_len;
i++){
     
    merge[k++]= a[i];
 
   }
 
  }
     
   
  return merge;
 
   
 }
 
 
 public static boolean isOrderedArray(int [] array){
 
  if(array==null||array.length==0){
     
   return false;
 
  }
     
   
  for(int i = 0;
    iarray.length-1;
i++){
     
   if(array[i]>
array[i+1]){
     
    return false;
 
   }
 
  }
     
  return true;
 
 }
 
  
 public static void main(String[] args) {
 
  int a [] = {
1,2,3,4,5}
    ;
 
  int b [] = {
2,3,4,5,6,7,8,9}
    ;
     
  int [] merge = merge(a,b);
     
  System.out.println(Arrays.toString(merge));
 
 }
 
}
     

算法的时间复杂度，取决于待合并的两个数组的长度，所以是O(M+N)，空间复杂度也是O(M+N)，即需要的归并数组的长度是M+N。

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！