当前位置： 移动技术网 > IT编程>开发语言>Java > Java实现合并两个有序序列算法示例

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

2019年07月19日  | 移动技术网IT编程  | 我要评论

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

算法实现

/**
 *
 * @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 3 5 6 7 8 9 10 44 45 55 59 66 70 188 788

更多关于java算法相关内容感兴趣的读者可查看本站专题：《java数据结构与算法教程》、《java操作dom节点技巧总结》、《java文件与目录操作技巧汇总》和《java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网