归并算法之有序数组合并算法实现
归并算法之有序数组合并算法实现
一个简单的有序数组合并算法：写一个函数，传入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(iarray[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。
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！