溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這期內(nèi)容當中小編將會給大家?guī)碛嘘P序列算法怎么利用Java進行合并，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。
問題描述
輸入：序列A<a0,a1,a2,...aq,aq+1,aq+2,...,ar>，其中a0<a1<...<aq,aq+1<aq+2<...<ar
輸出：序列B<b0,b1,...,br>,其中b0<b1<...<br
算法思想
創(chuàng)建一個長度為r的數(shù)組R，將A中的序列看作是兩個有序序列
B=A<a0,a1,a2,...,aq>
C=A<aq+1,aq+2,...,ar>
分別從B和C中拿取一個數(shù)進行比較，將較小的放入R，如果這個數(shù)在B中，則繼續(xù)取B中下一個最小的數(shù)；如果在C中，同樣操作。所有數(shù)都在R中。Ri=MIN(B)<=MIN(C)?MIN(B):MIN(C)
如果B或C沒有更多的數(shù)可以獲取，則將另一個序列的所有數(shù)填制R。
Ri=(MIN(B)MIN(C))
算法實現(xiàn)
/**
*
* @author Chuck
*
*/
public class Merge {
/**
* 合并兩個有序序列
* @param A 待合并序列
* @param q 第二個序列開始數(shù)組下標
* @return 合并后的新數(shù)組
*/
public static int[] merge(int [] A,int q){
//創(chuàng)建數(shù)組
int n = A.length;
int [] R = new int[n];
int i = 0;
int j = q+1;
int k = 0;
//如果兩個數(shù)組B 和 C中都有數(shù)據(jù)則選擇更小的加入到R中并獲取下一個
while(i<=q&&j<=n-1){
if(A[i]<=A[j]){
R[k]=A[i];
i++;
}else{
R[k]=A[j];
j++;
}
k++;
}
//如果B中有數(shù)據(jù)則把所有數(shù)據(jù)加入到R中
while(i<=q) R[k++] = A[i++];
//如果C中有數(shù)據(jù)則把所有數(shù)據(jù)加入到R中
while(j<n-1) R[k++] = A[j++];
return R;
}
public static void main(String [] args){
int [] A = {5,6,7,8,9,44,55,66,788,1,3,10,45,59,70,188};
int q = 8;
int [] R = Merge.merge(A, q);
for(int i=0;i<R.length;i++){
System.out.print(R[i] +" ");
}
}
}算法時間
f(n)=q+1+r−q=r+1
這里的r是數(shù)組的輸入規(guī)模，所以算法最壞情形運行時間為：
f(n)=O(n)
演示結果
1 3 5 6 7 8 9 10 44 45 55 59 66 70 188 788
上述就是小編為大家分享的序列算法怎么利用Java進行合并了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業(yè)資訊頻道。
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內(nèi)容。
