欢迎来到入门教程网!

Java编程

当前位置:主页 > 软件编程 > Java编程 >

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

来源:本站原创|时间:2020-01-10|栏目: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[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]; 
   } 
  } 
   
  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[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。

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

上一篇:Java编程实现从尾到头打印链表代码实例

栏    目:Java编程

下一篇:Java编程实现递增排序链表的合并

本文标题:归并算法之有序数组合并算法实现

本文地址:https://www.xiuzhanwang.com/a1/Javabiancheng/8461.html

网页制作CMS教程网络编程软件编程脚本语言数据库服务器

如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

联系QQ:835971066 | 邮箱:835971066#qq.com(#换成@)

Copyright © 2002-2020 脚本教程网 版权所有