algorithme de tri de structure de données Java (2) tri par fusion

Cet article présente principalement le tri par fusion de l'algorithme de tri des structures de données Java. Il analyse en détail les principes, les techniques de mise en œuvre et les précautions associées du tri par fusion sur la base d'exemples spécifiques. Les amis dans le besoin peuvent se référer à cet article

L'exemple décrit le tri par fusion de l'algorithme de tri des structures de données Java. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Les types de tri mentionnés ci-dessus organisent tous un groupe d'enregistrements dans une séquence ordonnée en fonction de la taille des mots-clés et de l'idée de le tri par fusion est : basé sur la fusion, fusionne deux ou plusieurs listes ordonnées dans une nouvelle liste ordonnée

Algorithme de tri par fusion : Supposons que la séquence initiale contient n enregistrements, Tout d'abord, traitez ces n enregistrements comme n sous-séquences ordonnées, chaque sous-séquence a une longueur de 1, puis fusionnez-les par paires pour obtenir n/2 longueurs de 2 (lorsque n est un nombre impair, la longueur de la dernière séquence est 1 ) sous-séquence ordonnée. Sur cette base, les sous-séquences ordonnées de longueur 2 sont fusionnées brillamment pour obtenir plusieurs sous-séquences ordonnées de longueur 4. Répétez cette opération jusqu'à ce qu'une séquence ordonnée de longueur n soit obtenue. Cette méthode est appelée : tri par fusion bidirectionnel (l'opération de base consiste à fusionner deux sous-séquences ordonnées adjacentes dans la séquence à trier en une séquence ordonnée).

Le code d'implémentation de l'algorithme est le suivant :

package exp_sort;
public class MergeSort {
  /**
   * 相邻两个有序子序列的合并算法
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void Merge(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    int i, j, k;
    mid = (low + high) / 2;
    i = low;
    k = 0;
    j = mid + 1;
    // compare two list
    while (i <= mid && j <= high) {
      if (src_array[i] <= src_array[j]) {
        des_array[k] = src_array[i];
        i = i + 1;
      } else {
        des_array[k] = src_array[j];
        j = j + 1;
      }
      k = k + 1;
    }
    // if 1 have,cat
    while (i <= mid) {
      des_array[k] = src_array[i];
      k = k + 1;
      i = i + 1;
    }
    while (j <= high) {
      des_array[k] = src_array[j];
      k = k + 1;
      j = j + 1;
    }
    for (i = 0; i < k; i++) {
      src_array[low + i] = des_array[i];
    }
  }
  /**
   * 2-路归并排序算法，递归实现
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void mergeSort(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    if (low < high) {
      mid = (low + high) / 2;
      mergeSort(src_array, low, mid, des_array);
      mergeSort(src_array, mid + 1, high, des_array);
      Merge(src_array, low, high, des_array);
    }
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array1[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    int array2[] = new int[array1.length];
    mergeSort(array1, 0, array1.length - 1, array2);
    System.out.println("\n----------after sort-------------");
    for (int ii = 0; ii < array1.length; ii++) {
      System.out.print(array1[ii] + " ");
    }
    System.out.println("\n");
  }
}

Explication du code :

Dans le tri par fusion, une passe de fusion nécessite plusieurs appels à l'algorithme de fusion bidirectionnelle. La complexité temporelle d'une passe de fusion est O(n). Parce qu'au plus n-1 comparaisons sont effectuées, où n est le nombre total d'éléments. S'il y a plusieurs nombres, c'est-à-dire lorsque n n'est pas 1, fusionnez et triez de manière récursive la première moitié des données et la seconde moitié des données pour obtenir les deux parties des données triées, puis fusionnez-les ensemble.

Analyse d'algorithme :

Cet algorithme est basé sur l'opération de fusion (également appelée algorithme de fusion, qui fait référence au processus de combinaison de deux séquences triées Un algorithme de tri efficace basé sur l'opération de fusion dans une séquence). Cet algorithme est une application très typique de la

méthode diviser et conquérir (pide and Conquer). Il divise le problème en quelques petits problèmes puis les résout de manière récursive, et l'étape de conquête est résolue en divisant l'étape divisée. Chaque réponse s'emboîte ; diviser pour régner est une utilisation très puissante de la récursivité. Remarque : Par rapport au tri rapide et au tri par tas, la plus grande caractéristique du tri par fusion est qu'il s'agit d'une méthode de tri stable . La vitesse est juste derrière le tri rapide, et elle est généralement utilisée pour les tableaux généralement désordonnés mais dont les sous-éléments sont relativement ordonnés.

Complexité :

La complexité temporelle est :

O(nlogn) - Cet algorithme est le meilleur et le plus efficace. Mauvais et la performance temporelle moyenne. La complexité spatiale est :
O(n)Le nombre d'opérations de comparaison est compris entre (nlogn) / 2 et nlogn - n + 1.
Le nombre d'opérations d'affectation est de (2nlogn). La complexité spatiale de l'algorithme de fusion est : 0 (n)
Il est difficile à utiliser pour le tri de la mémoire principale (le tri par fusion prend plus de mémoire. Le problème principal est que la fusion de deux tables triées nécessite une mémoire supplémentaire linéaire, ce qui coûte également de l'argent dans tout l'algorithme. Certaines opérations supplémentaires telles que copier des données dans un
tableau temporaire puis les recopier ralentiront sérieusement le tri) mais elles sont très efficaces et sont principalement utilisées pour le tri externe et pour des tâches importantes. les applications de tri internes, choisissent généralement le tri rapide.

Les étapes de l'opération de fusion sont les suivantes :

Étape 1 : Demander de l'espace pour que sa taille soit la somme des deux séquences triées. L'espace est utilisé pour stocker la séquence fusionnée

Étape 2 : Définir deux pointeurs, les positions initiales sont les positions de départ des deux séquences triées
Étape 3 : Comparez les éléments pointés par les deux pointeurs, Sélectionnez un élément relativement petit et placez-le dans l'espace de fusion, puis déplacez le pointeur vers la position suivante
Répétez l'étape 3 jusqu'à ce qu'un certain pointeur atteigne la fin de la séquence
Copiez directement tous les éléments restants de l'autre séquence jusqu'à la fin de la séquence de fusion

Les étapes du tri par fusion sont les suivantes (en supposant que la séquence comporte n éléments au total) :

Fusionner tous les deux nombres adjacents dans la séquence (merge), formant des séquences floor(n/2), chaque séquence contient deux éléments après le tri

Fusionner à nouveau les séquences ci-dessus, formant des séquences floor(n/4), chaque séquence en contient quatre éléments
Répétez l'étape 2 jusqu'à ce que tous les éléments soient triés

[Recommandations associées]

1

Algorithme de tri de structure de données Java (1) Tri par sélection d'arbre.

2.

Tutoriel détaillé sur Selection Sort_java en Java

3

Algorithme de tri de structure de données Java (3) Tri par sélection simple.

4. algorithme de tri de structure de données Java (4) tri par sélection

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!