Java实现合并两个有序序列算法示例
作者:软货 时间:2021-09-06 23:23:53
本文实例讲述了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程序设计有所帮助。
来源:http://blog.csdn.net/baidu_22502417/article/details/46638047
标签:Java,算法
0
投稿
猜你喜欢
基于Java接口回调详解
2023-11-09 00:03:11
java使用IO流对数组排序实例讲解
2023-09-04 02:24:19
java的url方式、本地方式获取json文件内容
2023-08-22 18:30:23
如何为Spring Cloud Gateway加上全局过滤器
2022-06-19 09:14:47
SpringCloud之微服务容错的实现
2023-11-29 02:02:22
java实现纸牌游戏之小猫钓鱼算法
2021-08-11 22:57:00
java之swing表格实现方法
2023-06-05 09:44:03
Java实现中国象棋的示例代码
2021-08-10 21:56:03
java同步之如何写一个锁Lock
2023-04-23 08:10:54
java8 利用reduce实现将列表中的多个元素的属性求和并返回操作
2021-09-29 06:53:38
java实现抽奖功能解析
2021-08-29 16:08:21
springboot结合vue实现增删改查及分页查询
2023-11-24 15:53:44
springboot如何统一设置时区
2022-01-26 18:16:39
C#8.0新语法using declaration
2023-10-23 00:57:54
微信公众号服务号推送模板消息设置方法(后端java)
2023-11-20 08:27:58
SpringBoot使用过滤器、拦截器和监听器的案例代码(Springboot搭建java项目)
2022-11-21 06:08:54
java 集合工具类Collections及Comparable和Comparator排序详解
2023-04-29 03:42:06
IDEA(jetbrain通用)使用教程图解
2023-04-15 04:05:49
SSM项目使用拦截器实现登录验证功能
2023-06-17 16:12:38
用JAVA实现杨辉三角实例
2023-08-28 16:45:23