Java implementation example of merging two ordered sequence algorithms

This article mainly introduces the algorithm for merging two ordered sequences in Java. It briefly describes the principle of the sequence merging algorithm and the specific operation steps and related implementation techniques for merging ordered sequences in Java. Friends in need can refer to it

The example in this article describes the Java implementation of merging two ordered sequence algorithms. Share it with everyone for your reference, the details are as follows:

Problem description

Input: sequenceA, wherea0Output: sequenceB, whereb0

Algorithmic idea

Create an array R of length r, and regard the sequence in A as two ordered sequences
B=A
C=A
From B and C respectively Take a number for comparison and put the smaller one into R. If the number is in B, continue to take the next smallest number in B; if it is in C, do the same. All numbers are in R.
Ri=MIN(B)<=MIN(C)?MIN(B):MIN(C)

If B or C has no more numbers to obtain, Then fill in R with all the numbers in the other sequence.

Ri=(MIN(B)MIN(C))

Algorithm implementation

/**
 *
 * @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] +" ");
    }
  }
}

Algorithm time

##f(n)=q+1+r−q=r+1

Here r is the input size of the array, so the worst-case running time of the algorithm is:

f(n)=O(n)

Demo results

1 3 5 6 7 8 9 10 44 45 55 59 66 70 188 788

The above is the detailed content of Java implementation example of merging two ordered sequence algorithms. For more information, please follow other related articles on the PHP Chinese website!