Exemple d'implémentation Java de fusion de deux algorithmes de séquence ordonnée

Cet article présente principalement l'algorithme Java pour fusionner deux séquences ordonnées. Il décrit brièvement le principe de l'algorithme de fusion de séquences ainsi que les étapes de fonctionnement spécifiques et les techniques de mise en œuvre associées pour fusionner des séquences ordonnées en Java. Les amis dans le besoin peuvent s'y référer. 🎜>

L'exemple de cet article décrit l'implémentation Java de la fusion de deux algorithmes de séquence ordonnée. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Description du problème

Entrée : séquence

A, oùa0
Sortie : séquenceB, oùb0

Idée algorithmique

Créer un tableau R de longueur r, et considérer la séquence dans A comme deux séquences ordonnées

B=AC=A

De B et C respectivement Prendre un nombre à comparer et mettez le plus petit dans R. Si le nombre est en B, continuez à prendre le prochain plus petit nombre en B s'il est en C, faites de même ; Tous les nombres sont en R.
Ri=MIN(B)<=MIN(C)?MIN(B):MIN(C)

S'il n'y a plus de nombres à obtenir de B ou C, remplissez R avec tous les nombres de l'autre séquence.

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

Mise en œuvre de l'algorithme

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

Temps de l'algorithme

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

où r est un tableau La taille d'entrée de >

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!