今天小編和大家分享的是歸并算法之有序數(shù)組合并算法實(shí)現(xiàn)，下面我們一塊來(lái)看一下吧。
一個(gè)簡(jiǎn)單的有序數(shù)組合并算法：寫一個(gè)函數(shù)，傳入2個(gè)有序的整數(shù)數(shù)組，返回一個(gè)有序的整數(shù)數(shù)組。實(shí)現(xiàn)相當(dāng)簡(jiǎn)單，創(chuàng)建一個(gè)長(zhǎng)度為這兩個(gè)長(zhǎng)度之和的數(shù)組，然后分別用三個(gè)指針指向這三個(gè)數(shù)組，找到這兩個(gè)數(shù)組中各個(gè)元素在合并數(shù)組中的位置并插入，直到某個(gè)數(shù)組指針到達(dá)尾部。再將另一個(gè)數(shù)組剩下的所有元素，直接放入歸并數(shù)組尾部。算法的簡(jiǎn)單實(shí)現(xiàn)，需要注意的是對(duì)參數(shù)的校驗(yàn)，判斷數(shù)組是否有序。
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(i<a_len&&j<b_len){
if(a[i]<b[j]){
merge[k++]=a[i++];
}else{
merge[k++]=b[j++];
}
}
//A數(shù)組全部合并完畢，將b數(shù)組剩余直接加入合并數(shù)組
if(i==a_len){
for(;j<b_len;j++){
merge[k++]=b[j];
}
}else{
for(;i<a_len;i++){
merge[k++]=a[i];
}
}
returnmerge;
}
publicstaticbooleanisOrderedArray(int[]array){
if(array==null||array.length==0){
returnfalse;
}
for(inti=0;i<array.length-1;i++){
if(array[i]>array[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));
}
}
算法的時(shí)間復(fù)雜度，取決于待合并的兩個(gè)數(shù)組的長(zhǎng)度，所以是O(M+N)，空間復(fù)雜度也是O(M+N)，即需要的歸并數(shù)組的長(zhǎng)度是M+N。
以上就是長(zhǎng)沙中公優(yōu)就業(yè)Java培訓(xùn)機(jī)構(gòu)小編介紹的“Java算法視頻教程：歸并算法”的內(nèi)容，希望對(duì)大家有幫助，如有疑問，請(qǐng)?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為你服務(wù)。
