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

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

1. public class MergeOrderedArray {
2. public static int[] merge(int [] a,int []b){
3.   if(!isOrderedArray(a)){
4.    System.out.println(" array a is not an ordered array.");
5.    return null;
6.   }
8.   if(!isOrderedArray(b)){
9.    System.out.println(" array b is not an ordered array.");
10.    return null;
11.   }
13.   int a_len = a.length;
14.   int b_len = b.length;
15.   int[] merge = new int[a_len+b_len];
16.   int i=0,j=0,k=0;
17.   while(i<a_len&&j<b_len){
18.    if(a[i]<b[j]){
19.     merge[k++]=a[i++];
20.    }else{
21.     merge[k++]=b[j++];
22.    }
23.   }
25.   //A数组全部合并完毕，将b数组剩余直接参与合并数组
26.   if(i==a_len){
27.    for(;j<b_len;j++){
28.     merge[k++]= b[j];
29.    }
30.   }else{
31.    for(;i<a_len;i++){
32.     merge[k++]= a[i];
33.    }
34.   }
36.   return merge;
38. }
40. public static boolean isOrderedArray(int [] array){
41.   if(array==null||array.length==0){
42.    return false;
43.   }
45.   for(int i = 0;i<array.length-1;i++){
46.    if(array[i]>array[i+1]){
47.     return false;
48.    }
49.   }
50.   return true;
51. }
53. public static void main(String[] args) {
54.   int a [] = {1,2,3,4,5};
55.   int b [] = {2,3,4,5,6,7,8,9};
56.   int [] merge = merge(a,b);
57.   System.out.println(Arrays.toString(merge));
58. }
59. }

复制代码

     算法的时间复杂度，取决于待合并的两个数组的长度，所以是O(M+N)，空间复杂度也是O(M+N)，即需要的归并数组的长度是M+N。

感激阅读，希望能协助到大家，谢谢大家对本站的支持！