Explication détaillée du tri par fusion de l'algorithme de tri PHP

Il existe de nombreux types d'algorithmes de tri PHP. Cet article présente principalement en détail les informations pertinentes sur le tri par fusion de la série d'algorithmes de tri. J'espère que cela pourra aider tout le monde.

Tri par fusion

Le tri par fusion (MERGE-SORT) est un algorithme de tri efficace basé sur des opérations de fusion. L'algorithme utilise la méthode diviser pour régner (pide et conquérir). une application très typique. 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.

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 avoir 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

<?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);
}

L'avez-vous déjà appris ? Tout le monde, essayez-le rapidement.

Recommandations associées :

Explication détaillée du tri par bucket dans l'algorithme de tri PHP series_php skills

Apprentissage des algorithmes de tri courants PHP

Exemple d'analyse des algorithmes de tri de base couramment utilisés en JavaScript

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!