Quel est le principe de l'algorithme de tri par fusion en Java et comment l'implémenter

1. Idée de base

Le tri par fusion est un algorithme de tri efficace basé sur des opérations de fusion. Cet algorithme est une application très typique utilisant la méthode diviser pour régner (Divide and Conquer). Fusionnez les sous-séquences déjà ordonnées pour obtenir une séquence complètement ordonnée ; c'est-à-dire que vous devez d'abord rendre chaque sous-séquence ordonnée, puis ordonner les segments de la sous-séquence. Si deux listes ordonnées sont fusionnées en une seule liste ordonnée, on parle de fusion bidirectionnelle.

2. Analyse de l'algorithme

1. Description de l'algorithme

Divisez la séquence d'entrée de longueur n en deux sous-séquences de longueur n/2 ; dans une séquence triée finale.

2. Analyse du processus

(1) Nous fusionnons maintenant les termes divisés [1] (indice de 0 à 0, inclus des deux côtés) et [28] indice de 1 à 1, inclus des deux côtés) ensemble.

(2), car 1 (séparation à gauche) <= 28 (séparation à droite), nous copions {rightPart} dans un nouveau tableau.

(3), comme le split de gauche est vide, nous copions 28 (split de droite) dans le nouveau tableau.

(4), nous copions les éléments du nouveau tableau dans le tableau d'origine.

(5), car 3 (séparation à gauche) <= 21 (séparation à droite), nous copions {rightPart} dans un nouveau tableau.

(6), parce que le split de gauche est vide, nous copions 21 (split de droite) dans le nouveau tableau.

(7), maintenant nous fusionnons les éléments divisés [1,28] (index de 0 à 1, inclus des deux côtés) et [3,21] (index de 2 à 3, inclus des deux côtés) ensemble .

(8), car 1 (scission gauche) <= 3 (scission droite), nous copions {rightPart} dans un nouveau tableau.

(9), car 28 (séparation à gauche) > 3 (séparation à droite), nous copions {rightPart} dans un nouveau tableau.

(10), car 28 (séparation à gauche) > 21 (séparation à droite), nous copions {rightPart} dans un nouveau tableau.

(11), comme le split de droite est vide, nous copions 28 (split de gauche) dans le nouveau tableau.

(12), nous copions les éléments du nouveau tableau dans le tableau d'origine.

(13), Nous fusionnons maintenant les termes divisés [11] (index de 4 à 4, les deux côtés inclus) et [7] index de 5 à 5, les deux côtés inclus) ensemble.

(14), car 11 (séparation à gauche) > 7 (séparation à droite), nous copions {rightPart} dans un nouveau tableau.

(15), parce que la division de droite est vide, nous copions 11 (scition de gauche) dans le nouveau tableau.

(16), nous copions les éléments du nouveau tableau dans le tableau d'origine.

(17), et ainsi de suite

(18), car 1 (séparation à gauche) <= 6 (séparation à droite), nous copions {rightPart} dans un nouveau tableau.

(19), car 3 (séparation à gauche) <= 6 (séparation à droite), nous copions {rightPart} dans un nouveau tableau.

(20), car 21 (séparation à gauche) > 6 (séparation à droite), nous copions {rightPart} dans un nouveau tableau.

(21), car 21 (séparation à gauche) > 7 (séparation à droite), nous copions {rightPart} dans un nouveau tableau.

(22), et ainsi de suite, nous copions les éléments du nouveau tableau dans le tableau d'origine.

3. Démonstration GIF

3.

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!