本文实例讲述了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