Java合并两个有序序列算法实现

问题描述

输入：序列A<a0,a1,a2,...aq,aq+1,aq+2,...,ar>$A$，其中a0<a1<...<aq,aq+1<aq+2<...<ar$a_0 <br> 输出：序列<nobr>B&lt;b0,b1,...,br&gt;,其中b0&lt;b1&lt;...&lt;br</nobr><script id="MathJax-Element-48" type="math/tex">B<b_0,b_1,...,b_r>,其中b_0<b_1<...<b_r$

算法思想

创建一个长度为r的数组R，将A中的序列看作是两个有序序列
B=A<a0,a1,a2,...,aq>$B = A$
C=A<aq+1,aq+2,...,ar>$C = A$
分别从B和C中拿取一个数进行比较，将较小的放入R，如果这个数在B中，则继续取B中下一个最小的数；如果在C中，同样操作。所有数都在R中。
Ri=MIN(B)<=MIN(C)?MIN(B):MIN(C)$R_i = { MIN(B)<=MIN(C)?MIN(B):MIN(C)}$
如果B或C没有更多的数可以获取，则将另一个序列的所有数填制R。
Ri=(MIN(B)MIN(C))$R_i = {MIN(B) choose MIN(C)}$

算法实现

/**
 * 
 * @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$f(n) = q+1 + r- q = r + 1$

这里的r是数组的输入规模，所以算法最坏情形运行时间为：

f(n)=O(n)$f(n) = O(n)$

演示结果

1 3 5 6 7 8 9 10 44 45 55 59 66 70 188 788