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