두 개의 정렬된 시퀀스 알고리즘을 병합하는 Java 구현 예

이 글에서는 주로 Java에서 두 개의 정렬된 시퀀스를 병합하는 알고리즘을 소개합니다. 시퀀스 병합 알고리즘의 원리와 Java에서 정렬된 시퀀스를 병합하는 구체적인 작업 단계 및 관련 구현 기술을 간략하게 설명합니다. 이 기사

두 개의 정렬된 시퀀스 알고리즘을 병합하는 Java 구현을 설명합니다. 참조용으로 모든 사람과 공유하세요. 세부정보는 다음과 같습니다.

문제 설명

입력: 시퀀스A, 여기서 a0출력: 시퀀스 B 그 중 b0

알고리즘 아이디어

길이가 r인 배열 R을 만들고 A의 시퀀스를 두 개의 순서 시퀀스로 간주합니다
B= A
C=A
비교를 위해 B와 C에서 숫자를 취하고 더 작은 Put을 비교합니다. R에 넣습니다. 숫자가 B에 있으면 B에서 다음으로 가장 작은 숫자를 계속 사용하고 C에 있으면 동일한 작업을 수행합니다. 모든 숫자는 R에 있습니다.
Ri=MIN(B)<=MIN(C)?MIN(B):MIN(C)Ri=MIN(B)<=MIN(C)?MIN(B):MIN(C)

如果B或C没有更多的数可以获取，则将另一个序列的所有数填制R。

Ri=(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 구현 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!