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

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

jacklove

Libérer： 2023-04-02 10:18:01

original

2161 Les gens l'ont consulté

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.

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

Copier après la connexion

Ce qui précède est tout le contenu de cet article, j'espère qu'il sera utile à l'étude de chacun, J'espère également que tout le monde soutiendra le site Web chinois php.

Articles qui pourraient vous intéresser :

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!