Maison > Article > développement back-end > Explication détaillée du tri par fusion dans l'algorithme de tri PHP series_php skills
Cet article présente principalement les informations pertinentes de la série d'algorithmes de tri PHP Merge Sort en détail. Il a une certaine valeur de référence. Les amis intéressés peuvent se référer à
Merge Sort
<.>Le tri par fusion (MERGE-SORT) est un algorithme de tri efficace basé sur l'opération de fusion. Cet algorithme est une application très typique de la méthode diviser pour mieux régner (pide 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.Processus de fusion
Le cœur du tri par fusion est de savoir comment fusionner deux séquences ordonnées. Supposons qu'il existe deux tableaux ordonnés et comparez les deux tableaux ordonnés. Prenez le premier élément. , selon le plus petit, 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. Lorsqu'un tableau est récupéré et qu'il n'y a aucun élément, vous pouvez ajouter les éléments restants de. l'autre tableau 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, le dernier. une séquence ne peut avoir qu’un seul élément.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 fusion5,6,12,25,37,53,89,92,98 Implémentation du code PHP<?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); }
Explication détaillée du tri par sélection directe de la série d'algorithmes de tri PHP
Explication détaillée du tri par insertion de la série d'algorithmes de tri PHP
Explication de l'algorithme de tri par bucket implémenté en PHP
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!