Java实现合并两个有序序列算法示例
本文实例讲述了Java实现合并两个有序序列算法。分享给大家供大家参考,具体如下:
问题描述
输入:序列A 算法思想 创建一个长度为r的数组R,将A中的序列看作是两个有序序列 如果B或C没有更多的数可以获取,则将另一个序列的所有数填制R。 Ri=(MIN(B)MIN(C)) 算法实现 算法时间 f(n)=q+1+r−q=r+1 这里的r是数组的输入规模,所以算法最坏情形运行时间为: f(n)=O(n) 演示结果 更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》 希望本文所述对大家java程序设计有所帮助。 声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。
B=A
C=A
分别从B和C中拿取一个数进行比较,将较小的放入R,如果这个数在B中,则继续取B中下一个最小的数;如果在C中,同样操作。所有数都在R中。
Ri=MIN(B)<=MIN(C)?MIN(B):MIN(C)
/**
*
*@authorChuck
*
*/
publicclassMerge{
/**
*合并两个有序序列
*@paramA待合并序列
*@paramq第二个序列开始数组下标
*@return合并后的新数组
*/
publicstaticint[]merge(int[]A,intq){
//创建数组
intn=A.length;
int[]R=newint[n];
inti=0;
intj=q+1;
intk=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
135678910444555596670188788