Aperçu
La méthode de tri de fusion consiste à fusionner deux (ou plus de deux) des tables ordonnées dans une nouvelle table ordonnée, c'est-à-dire diviser la séquence à tri en plusieurs sous-séquences, chaque sous-séquence est ordonnée. Ensuite, les sous-séquences ordonnées sont fusionnées dans la séquence ordonnée globale.
Le tri de fusion est mis en œuvre à l'aide de la récursivité, qui appartient à "diviser et conquérir". Le tableau cible est divisé en deux du milieu, puis les deux tableaux sont triés séparément. Une fois le tri terminé, les deux tableaux sont "fusionnés" ensemble. La chose la plus importante dans le tri de fusion est le processus de "fusion". Dans le processus de fusion, un espace supplémentaire cohérent avec les deux tableaux qui doivent être fusionnés sont nécessaires.
Image de reproduction:
étape
Appliquez de l'espace pour que sa taille soit la somme de deux séquences triées. Cet espace est utilisé pour stocker la séquence fusionnée pour définir deux pointeurs. La position initiale est la position de départ des deux séquences triées, comparer les éléments pointés par les deux pointeurs, sélectionner des éléments relativement petits et les mettre dans l'espace fusionné et déplacer le pointeur vers la position suivante. Répétez l'étape 3 jusqu'à ce qu'un pointeur atteigne l'extrémité de la séquence. Copiez tous les éléments restants de l'autre séquence directement à la fin de la séquence fusionnée.
Données brutes:
3 5 2 6 2
La condition préalable à la fusion est de séparer les tableaux, de les diviser en deux, puis de les diviser en deux, et ils ne peuvent plus être divisés et les fusionner.
Le premier tour est séparé, l'index 2 ((0 + 4) / 2 = 2) est le milieu
[3 5 2] [6 2]
Le deuxième cycle de séparation, séparé [3 5 2]
[3 5] [2] [6 2]
Le troisième cycle de séparation, séparé [3 5]
[3] [5] [2] [6 2]
Fusionner [3] [5]
[3 5] [2] [6 2]
Fusionner [3 5] [2]
[2 3 5] [6 2]
Le quatrième tour est séparé, se sépare [6 2]
[2 3 5] [6] [2]
Fusionner [6] [2]
[2 3 5] [2 6]
Fusion [2 3 5] [2 6]
[2 2 3 5 6]
Implémentation du code (Java)
package com.coder4j.main.arithmetic.sorting; public class Merge {private static int Mark = 0; / ** * Merge Sort * * @param Array * @param Low * @param high * @return * / private static int [] srie (int [] array, int low, int high) {int mid = (low + high) / 2; if (Low <High) {Mark ++; System.out.println ("Throwth in Progress" + Mark + "Séparation ultérieure, Get"); System.out.println ("[" + Low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]"); // le tri du tableau gauche (tableau, bas, mi-); // le tri du tableau droit (tableau, mid + 1, haut); // la fusion gauche et droite (tableau, bas, milieu, haut); } Return Array; } / ** * Merge le tableau * * @param array * @param low * @param mid * @param high * / private static void merge (int [] array, int low, int mid, int high) {System.out.println ("Merge: [" + Low + "-" + mid + "] et [" + (mid + 1) + "-" + high + "]"); int [] temp = new int [high - bas + 1]; int i = bas; // pointeur gauche int j = mid + 1; // pointeur droit int k = 0; // déplace d'abord le nombre plus petit vers le nouveau tableau while (i <= mid && j <= high) {if (array [i] <array [j]) {temp [k ++] = array [i ++]; } else {temp [k ++] = array [j ++]; }} // Il peut y avoir des éléments restants dans l'un des deux tableaux // déplacez le numéro restant à gauche dans le tableau while (i <= mid) {temp [k ++] = array [i ++]; } // Déplacez le numéro restant à droite dans le tableau tandis (j <= high) {temp [k ++] = array [j ++]; } // écraser les nombres dans le nouveau tableau de tableau pour (int m = 0; m <temp.length; m ++) {array [m + low] = temp [m]; }} / ** * Merge Sort * * @param array * @return * / public static int [] tri (int [] array) {return tri (array, 0, array.length - 1); } public static void main (String [] args) {int [] array = {3, 5, 2, 6, 2}; int [] trid = tri (array); System.out.println ("résultat final"); pour (int i: tri) {System.out.print (i + ""); }}}Résultats de la sortie de test:
La première séparation est effectuée, et le [0-2] [3-4] est effectué, et la deuxième séparation est effectuée, et le [0-1] [2-2] est effectué, et la troisième séparation est en cours [3-3] [4-4] Fusiter: [3-3] et [4-4] fusionner: [0-2] et [3-4] Résultat final 2 2 3 5 6
Après les tests, il est cohérent avec les résultats de l'exemple.