Java實現(xiàn)合并兩個有序序列算法示例
本文實例講述了Java實現(xiàn)合并兩個有序序列算法。分享給大家供大家參考，具體如下：
問題描述
輸入：序列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算法相關內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結構與算法教程》、《Java操作DOM節(jié)點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設計有所幫助。
相關文章
spring?@Transactional注解中常用參數(shù)詳解
這篇文章主要介紹了spring?@Transactional注解中常用參數(shù)詳解,事物注解方式:?@Transactional,本文結合實例代碼給大家介紹的非常詳細,需要的朋友可以參考下2024-02-02
Jasypt的StandardPBEByteEncryptor使用源碼解析
這篇文章主要介紹了Jasypt的StandardPBEByteEncryptor使用源碼解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-09-09
Spring中allowedOriginPatterns和allowedOrigins方法有何不同詳解
這篇文章主要給大家介紹了關于Spring中allowedOriginPatterns和allowedOrigins方法有何不同,allowedOriginPatterns和allowedOrigins都是用來設置允許跨域請求的來源,需要的朋友可以參考下2023-10-10
這篇文章主要介紹了關于mybatis使用${}時sql注入的問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-12-12
SpringMVC接收復雜集合對象（參數(shù)）代碼示例
這篇文章主要介紹了SpringMVC接收復雜集合對象（參數(shù)）代碼示例，舉接收List<String>、List<User>、List<Map<String,Object>>、User[]、User(bean里面包含List)幾種較為復雜的集合參數(shù)，具有一定參考價值，需要的朋友可以了解下。2017-11-11
這篇文章主要介紹了Java中指定時區(qū)的3種方法,本文是一個JAVA項目和.NET項目通訊時遇到的問題,本文給出JAVA中的3種解決方法,需要的朋友可以參考下2015-02-02
TOMCAT內(nèi)存溢出及大小調(diào)整的實現(xiàn)方法
下面小編就為大家?guī)硪黄猅OMCAT內(nèi)存溢出及大小調(diào)整的實現(xiàn)方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-05-05
這篇文章主要介紹了Dubbo服務無法注冊到ZK上問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-05-05
這篇文章主要介紹了Java 5億整數(shù)大文件怎么排序，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-03-03
這篇文章主要介紹了Gradle的基本使用方法，幫助大家更好的理解和學習Gradle的相關知識，感興趣的朋友可以了解下2021-03-03