Explication détaillée du type de fusion de la série d'algorithmes de tri PHP

Cet article explique l'explication détaillée du tri par fusion des séries d'algorithmes de tri PHP.

Tri par fusion

Le tri par fusion (MERGE-SORT) est un algorithme de tri efficace basé sur des opérations de fusion. Cet algorithme est un algorithme de tri très efficace qui utilise la méthode diviser pour régner. 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.

Processus de fusion

Le cœur du tri par fusion est de savoir comment fusionner deux séquences ordonnées. Supposons qu'il y ait deux tableaux ordonnés. Comparez les premiers éléments des deux tableaux ordonnés, lequel est le plus petit ? prenez qui vous voulez et placez l'élément dans le troisième tableau. Après l'avoir pris, l'élément sera supprimé dans le tableau correspondant, et ainsi de suite. Lorsque vous obtenez un tableau qui n'a aucun élément, vous pouvez ajouter les éléments restants de l'autre. tableau. Les éléments sont ajoutés directement au troisième tableau.

Principe

1. Fusionner tous les deux nombres adjacents dans la séquence pour former des séquences ceil(n/2) Après le tri, chaque séquence contient deux éléments, et la dernière séquence Il ne peut y en avoir qu'un. un élément.

2. Fusionnez à nouveau les séquences ci-dessus pour former des séquences ceil(n/4) Chaque séquence contient quatre éléments, et la dernière séquence ne peut contenir que trois éléments ou moins.

3. Répétez l'étape 2 jusqu'à ce que tous les éléments soient triés.

Exemple

Trier le tableau [53,89,12,6,98,25,37,92,5]

Après la première fusion

(53,89),12, (6,98),(25,37),(5,92)

Après la deuxième fusion

(12,53, 89), (6,25,37,98),(5,92)

Après la troisième fusion

(6,12,25,37,53,89,98) ,(5, 92)

Après la quatrième fusion

5,6,12,25,37,53,89,92,98

Implémentation du code PHP

function merge_sort($arr){
 
$length=count($arr);
 
if($length<=1){
 
return $arr;
 
}
 
//分解数组，递归排序
 
$half=ceil($length/2);
 
$arr2=array_chunk($arr,$half);
 
$left=merge_sort($arr2[0]);
 
$right=merge_sort($arr2[1]);
 
while(count($left)&&count($right)){
 
if($left[0]<$right[0]){
 
$reg[]=array_shift($left);
 
}else{
 
$reg[]=array_shift($right);
 
}
 
}
 
return array_merge($reg,$left,$right);
 
}

Cet article explique l'explication détaillée du tri par fusion dans la série d'algorithmes de tri PHP. Veuillez faire attention au site Web chinois PHP pour le contenu connexe.

Recommandations associées :

Fonctionnement cohérent de la base de données du framework thinkPHP5 : détails d'utilisation de cache()

Interface PHP héritage multiple et tarits Détails du didacticiel sur la façon d'obtenir plusieurs effets d'héritage

Tutoriel PHP sur la façon d'obtenir la date de début et la date de fin de la semaine d'une certaine année

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!