Rumah >Java >javaTutorial >Java合并两个有序序列算法的实现示例
这篇文章主要介绍了Java实现合并两个有序序列算法,简单描述了序列合并算法的原理与java合并有序序列的具体操作步骤及相关实现技巧,需要的朋友可以参考下
本文实例讲述了Java实现合并两个有序序列算法。分享给大家供大家参考,具体如下:
问题描述
输入:序列Ac69a9299fa7a1308670cd5c77f732f20,其中a038c508156832a06a68d194087cdd0eec,其中b0fdb5580032d962d77115a3213f3f0778
C=A592b05092b1df436d75d38dbcd7381be
分别从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
Atas ialah kandungan terperinci Java合并两个有序序列算法的实现示例. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!