首页 > Java资讯 > Java算法视频教程:归并算法

Java算法视频教程:归并算法

更新时间:2020-02-28 13:06 浏览69次 来源:动力节点


  今天小编和大家分享的是归并算法之有序数组合并算法实现,下面我们一块来看一下吧。


Java算法视频教程:归并算法


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


  publicclassMergeOrderedArray{


  publicstaticint[]merge(int[]a,int[]b){


  if(!isOrderedArray(a)){


  System.out.println("arrayaisnotanorderedarray.");


  returnnull;


  }


  if(!isOrderedArray(b)){


  System.out.println("arraybisnotanorderedarray.");


  returnnull;


  }


  inta_len=a.length;


  intb_len=b.length;


  int[]merge=newint[a_len+b_len];


  inti=0,j=0,k=0;


  while(i<a_len&&j<b_len){


  if(a[i]<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[i];


  }


  }


  returnmerge;


  }


  publicstaticbooleanisOrderedArray(int[]array){


  if(array==null||array.length==0){


  returnfalse;


  }


  for(inti=0;i<array.length-1;i++){


  if(array[i]>array[i+1]){


  returnfalse;


  }


  }


  returntrue;


  }


  publicstaticvoidmain(String[]args){


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


  intb[]={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算法视频教程:归并算法”的内容,希望对大家有帮助,如有疑问,请在线咨询,有专业老师随时为你服务。


热门课程推荐

全部班型支持免费试学

动力节点在线报名表(此信息已加密,请放心填写)

返回顶部