查看: 182|回复: 0

Java视频教程之归并算法之有序数组合并算法实现

发表于 2018-5-25 10:34:08
        近期扣丁学堂Java在线学习小编会给大家分享一些比较实用的Java技能,对java开发感兴趣的小伙伴们可以关注了解一下,本篇文章小编和大家分享的是归并算法之有序数组合并算法实现,下面我们一块来看一下吧。
        一个简单的有序数组合并算法:写一个函数,传入 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(i<a_len&&j<b_len){
   if(a<b[j]){
    merge[k++]=a[i++];
   }else{
    merge[k++]=b[j++];
   }
  }
   
  //A数组全部合并完毕,将b数组剩余直接加入合并数组
  if(i==a_len){
   for(;j<b_len;j++){
    merge[k++]= b[j];
   }
  }else{
   for(;i<a_len;i++){
    merge[k++]= a;
   }
  }
   
  return merge;
   
}
public static boolean isOrderedArray(int [] array){
  if(array==null||array.length==0){
   return false;
  }
   
  for(int i = 0;i<array.length-1;i++){
   if(array>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。
        以上是扣丁学堂Java在线学习小编简单为大家分享的归并算法之有序数组合并算法实现,希望对小伙伴们会有所帮助。想要了解更多Java开发方面的问题的话,小伙伴们可以登录扣丁学堂官网咨询。扣丁学堂是专业的Java培训机构,不仅有专业的老师和与时俱进的课程体系,还有大量的Java视频教程供学员观看学习,想要学好Java开发的小伙伴快快行动吧。Java技术交流群:670348138。
  文章转载自:扣丁学堂http://www.codingke.com/



回复

使用道具 举报