归并算法之有序数组合并算法实现
归并算法之有序数组合并算法实现
一个简单的有序数组合并算法:写一个函数,传入 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。
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
您可能感兴趣的文章
- 01-10跟我学Java Swing之游戏设计(2)
- 01-10EJB轻松进阶之一
- 01-10SWT(JFace)体验之FormLayout布局
- 01-10SWT(JFace)体验之RowLayout布局
- 01-10SWT(JFace)体验之StyledText类
- 01-10SWT(JFace)体验之GridLayout布局
- 01-10选择java的理由:java之父访谈实录
- 01-10跟我学Java Swing之游戏设计(1)
- 01-10SWT(JFace)体验之ApplicationWindow
- 01-10SWT(JFace)体验之复制粘贴
阅读排行
本栏相关
- 01-10Java咖啡馆(1)——叹咖啡
- 01-10JVM的垃圾回收机制详解和调优
- 01-10Java Socket编程(三) 服务器Sockets
- 01-10Java进阶:Struts多模块的技巧
- 01-10J2SE 1.5版本的新特性一览
- 01-10Java Socket编程(一) Socket传输模式
- 01-10Java运行时多态性的实现
- 01-10Java Socket编程(二) Java面向连接的类
- 01-10Java Socket编程(四) 重复和并发服务
- 01-10Java经验点滴:处理没有被捕获的异常
随机阅读
- 08-05dedecms(织梦)副栏目数量限制代码修改
- 08-05织梦dedecms什么时候用栏目交叉功能?
- 01-11Mac OSX 打开原生自带读写NTFS功能(图文
- 01-10C#中split用法实例总结
- 01-10delphi制作wav文件的方法
- 01-10SublimeText编译C开发环境设置
- 08-05DEDE织梦data目录下的sessions文件夹有什
- 04-02jquery与jsp,用jquery
- 01-10使用C语言求解扑克牌的顺子及n个骰子
- 01-11ajax实现页面的局部加载