本文實例講述了Java實現合并兩個有序序列算法。分享給大家供大家參考，具體如下：
問題描述
輸入：序列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
算法思想
創建一個長度為r的數組R，將A中的序列看作是兩個有序序列
B=A<a0,a1,a2,...,aq>
C=A<aq+1,aq+2,...,ar>
分別從B和C中拿取一個數進行比較，將較小的放入R，如果這個數在B中，則繼續取B中下一個最小的數；如果在C中，同樣操作。所有數都在R中。
Ri=MIN(B)<=MIN(C)?MIN(B):MIN(C)
如果B或C沒有更多的數可以獲取，則將另一個序列的所有數填制R。
Ri=(MIN(B)MIN(C))
算法實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
/** * * @author Chuck * */public class Merge { /** * 合并兩個有序序列 * @param A 待合并序列 * @param q 第二個序列開始數組下標 * @return 合并后的新數組 */ public static int[] merge(int [] A,int q){ //創建數組 int n = A.length; int [] R = new int[n]; int i = 0; int j = q+1; int k = 0; //如果兩個數組B 和 C中都有數據則選擇更小的加入到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中有數據則把所有數據加入到R中 while(i<=q) R[k++] = A[i++]; //如果C中有數據則把所有數據加入到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是數組的輸入規模，所以算法最壞情形運行時間為：
f(n)=O(n)
演示結果
|
1
|
1 3 5 6 7 8 9 10 44 45 55 59 66 70 188 788 |
希望本文所述對大家java程序設計有所幫助。
原文鏈接：http://blog.csdn.net/baidu_22502417/article/details/46638047
