歸并算法之有序數組合并算法實現
一個簡單的有序數組合并算法:寫一個函數,傳入 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。
感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!
|
新聞熱點
疑難解答