Java-Implementierungsbeispiel für die Zusammenführung zweier geordneter Sequenzalgorithmen

In diesem Artikel wird hauptsächlich der Algorithmus zum Zusammenführen zweier geordneter Sequenzen in Java vorgestellt. Er beschreibt kurz das Prinzip des Sequenzzusammenführungsalgorithmus und die spezifischen Operationsschritte und zugehörigen Implementierungstechniken zum Zusammenführen geordneter Sequenzen in Java

Das Beispiel in diesem Artikel beschreibt die Java-Implementierung der Zusammenführung zweier geordneter Sequenzalgorithmen. Teilen Sie es allen als Referenz mit. Die Details lauten wie folgt:

Problembeschreibung

Eingabe: Sequenz A, wobeia0Ausgabe: SequenzB, wobeib0

Algorithmusidee

Erstellen Sie ein Array R der Länge r und betrachten Sie die Sequenz in A als zwei geordnete Sequenzen
B=A
C=A
Von B bzw. C Nehmen eine Zahl zum Vergleich und setze die kleinere in R ein. Wenn die Zahl in B liegt, nimm weiter die nächstkleinere Zahl in B; wenn sie in C liegt, mache dasselbe. Alle Zahlen sind in R.
Ri=MIN(B)<=MIN(C)?MIN(B):MIN(C)

Wenn von B oder C keine weiteren Zahlen mehr vorhanden sind, füllen Sie R mit allen Zahlen in der anderen Reihenfolge aus.

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

Algorithmusimplementierung

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

Algorithmuszeit

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

wobei r ein Array ist Die Eingabegröße von >

Das obige ist der detaillierte Inhalt vonJava-Implementierungsbeispiel für die Zusammenführung zweier geordneter Sequenzalgorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!