欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-03-01 08:48:04
本文实例讲述了java实现合并两个有序序列算法。分享给大家供大家参考,具体如下: 问题描述 输入:序列a

本文实例讲述了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程序设计有所帮助。