Java實(shí)現(xiàn)合并兩個(gè)有序序列算法示例
本文實(shí)例講述了Java實(shí)現(xiàn)合并兩個(gè)有序序列算法。分享給大家供大家參考，具體如下：
問題描述
輸入：序列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)建一個(gè)長度為r的數(shù)組R，將A中的序列看作是兩個(gè)有序序列
B=A<a0,a1,a2,...,aq>
C=A<aq+1,aq+2,...,ar>
分別從B和C中拿取一個(gè)數(shù)進(jìn)行比較，將較小的放入R，如果這個(gè)數(shù)在B中，則繼續(xù)取B中下一個(gè)最小的數(shù)；如果在C中，同樣操作。所有數(shù)都在R中。
Ri=MIN(B)<=MIN(C)?MIN(B):MIN(C)
如果B或C沒有更多的數(shù)可以獲取，則將另一個(gè)序列的所有數(shù)填制R。
Ri=(MIN(B)MIN(C))
算法實(shí)現(xiàn)
/**
*
* @author Chuck
*
*/
public class Merge {
/**
* 合并兩個(gè)有序序列
* @param A 待合并序列
* @param q 第二個(gè)序列開始數(shù)組下標(biāo)
* @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;
//如果兩個(gè)數(shù)組B 和 C中都有數(shù)據(jù)則選擇更小的加入到R中并獲取下一個(gè)
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] +" ");
}
}
}
算法時(shí)間
f(n)=q+1+r−q=r+1
這里的r是數(shù)組的輸入規(guī)模，所以算法最壞情形運(yùn)行時(shí)間為：
f(n)=O(n)
演示結(jié)果
1 3 5 6 7 8 9 10 44 45 55 59 66 70 188 788
更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設(shè)計(jì)有所幫助。
相關(guān)文章
詳解最簡單易懂的Spring Security 身份認(rèn)證流程講解
這篇文章主要介紹了詳解最簡單易懂的Spring Security 身份認(rèn)證流程講解，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2019-03-03
SpringCloud Webflux過濾器增加header傳遞方式
這篇文章主要介紹了SpringCloud Webflux過濾器增加header傳遞方式，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02
淺談HashMap、HashTable的key和value是否可為null
這篇文章主要介紹了淺談HashMap、HashTable的key和value是否可為null，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-09-09
字符串拼接是我們在Java代碼中比較經(jīng)常要做的事情,就是把多個(gè)字符串拼接到一起,下面這篇文章主要給大家總結(jié)介紹了關(guān)于Java中字符串常見的一些拼接方式,需要的朋友可以參考下2023-04-04
這篇文章主要為大家詳細(xì)介紹了Mybatis構(gòu)建SQL，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-07-07
mybatis?報(bào)錯(cuò)顯示sql中有兩個(gè)limit的解決
這篇文章主要介紹了mybatis?報(bào)錯(cuò)顯示sql中有兩個(gè)limit的解決，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-10-10
java的三種隨機(jī)數(shù)生成方式的實(shí)現(xiàn)方法
這篇文章主要介紹了java的三種隨機(jī)數(shù)生成方式的實(shí)現(xiàn)方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
這篇文章主要介紹了Java編程中最基礎(chǔ)的文件和目錄操作方法詳解,是Java入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-11-11
Java實(shí)現(xiàn)獲取Excel中的表單控件
Excel中可通過【開發(fā)工具】菜單欄下插入表單控件，如文本框、單選按鈕、復(fù)選框、組合框等等。本文將利用Java實(shí)現(xiàn)獲取Excel中的表單控件，需要的可以參考一下2022-05-05
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)微信紅包，拼手氣紅包，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11