Algorithme de tri PHP Merging Sort (Merging Sort)

Cet article présente principalement le tri par fusion de l'algorithme de tri PHP. Il analyse en détail les principes, les définitions, les méthodes d'utilisation et les précautions de fonctionnement associées avec des exemples. Les amis dans le besoin peuvent s'y référer

L'exemple de cet article décrit l'algorithme de tri Merging Sort de PHP. Partagez-le avec tout le monde pour votre référence, comme suit :

Idée de base :

Tri par fusion : il est implémenté en utilisant l'idée de ​​fusion (fusion) Méthode de tri. Son principe est qu'en supposant que la séquence initiale contient n éléments, elle peut être considérée comme n sous-séquences ordonnées, chaque sous-séquence a une longueur de 1, puis fusionnée par paires pour obtenir ⌈ n / 2⌉ (⌈ x ⌉ signifie non Le plus petit entier inférieur au tri par fusion bidirectionnel.

1. Le processus de fusion :

a[i] prend la partie avant du tableau a (déjà trié), a[j] prend la dernière partie de la partie du tableau a (déjà triée)

le tableau r stocke le tableau a trié

compare les tailles de a[i] et a[j], si a[i] ≤ a[ j ], puis copiez l'élément a[i] dans la première liste ordonnée dans r[k], et ajoutez 1 à i et k respectivement ; sinon, copiez l'élément a[j] dans la deuxième liste ordonnée. Copiez-le dans r[ ; k], et ajoutez 1 à j et k respectivement. Ce cycle continue jusqu'à ce que l'une des listes ordonnées soit récupérée, puis copie les éléments restants de l'autre liste ordonnée vers r de l'indice k vers l'élément de l'indice t. Nous utilisons généralement la récursion pour implémenter l'algorithme de tri par fusion. Tout d'abord, divisez l'intervalle à trier [s, t] en deux au milieu, puis triez la sous-plage de gauche, puis triez la sous-plage de droite et enfin effectuez une sous-plage de gauche. opération de fusion sur les intervalles gauche et droit Fusionner en intervalles ordonnés [s,t].

2. Opération de fusion :

L'opération de fusion (fusion), également appelée algorithme de fusion, fait référence à la méthode de fusion de deux séquences séquentielles en une seule séquence séquentielle.

S'il existe une séquence {6, 202, 100, 301, 38, 8, 1>

État initial : 6, 202, 100, 301, 38, 8, 1

Après la première fusion : {6,202}, {100,301}, {8,38}, {1}, nombre de comparaisons : 3

Après la deuxième fusion : {6,100,202,301}, {1 ; ,8,38}, nombre de comparaisons : 4 ;

Après la troisième fusion : {1,6,8,38,100,202,301}, nombre de comparaisons :

Le nombre total de comparaisons est : 3+4+4=11,;

Le nombre inverse est 14 ;

Description de l'algorithme :

Le principe de fonctionnement de. l'opération de fusion est la suivante :

Étape 1 : Demander de l'espace pour que sa taille soit la somme des deux séquences triées. Cet espace est utilisé pour stocker la séquence fusionnée

Étape 2 : Définissez deux pointeurs. Les positions initiales sont les positions de départ des deux séquences triées

Étape 3 : Comparez les éléments pointés par les deux pointeurs, sélectionnez l'élément relativement petit et placez-le dans l'espace de fusion, puis déplacez-le. le pointeur vers la position suivante

Répétez l'étape 3 jusqu'à ce qu'un pointeur dépasse la fin de la séquence

Copiez tous les éléments restants de l'autre séquence directement à la fin de la séquence fusionnée

Implémentation de l'algorithme :

Jetons d'abord un coup d'œil à la partie fonction principale :

//交换函数
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//归并算法总函数
function MergeSort(array &$arr){
  $start = 0;
  $end = count($arr) - 1;
  MSort($arr,$start,$end);
}

Dans la fonction totale, nous n'avons appelé qu'une seule fonction MSort() Parce que nous voulons utiliser des appels récursifs, nous encapsulons MSort().

Jetons un coup d'œil à la fonction

 : MSort()

function MSort(array &$arr,$start,$end){
  //当子序列长度为1时，$start == $end，不用再分组
  if($start < $end){
    $mid = floor(($start + $end) / 2); //将 $arr 平分为 $arr[$start - $mid] 和 $arr[$mid+1 - $end]
    MSort($arr,$start,$mid);  //将 $arr[$start - $mid] 归并为有序的$arr[$start - $mid]
    MSort($arr,$mid + 1,$end);  //将 $arr[$mid+1 - $end] 归并为有序的 $arr[$mid+1 - $end]
    Merge($arr,$start,$mid,$end);    //将$arr[$start - $mid]部分和$arr[$mid+1 - $end]部分合并起来成为有序的$arr[$start - $end]
  }
}

La fonction

ci-dessus implémente la division du tableau en deux puis divisez-le en deux (jusqu'à ce que la longueur de la sous-séquence soit de 1), puis fusionnez les sous-séquences ensemble. MSort()

C'est maintenant notre fonction d'opération de fusion

:Merge()

//归并操作
function Merge(array &$arr,$start,$mid,$end){
  $i = $start;
  $j=$mid + 1;
  $k = $start;
  $temparr = array();
  while($i!=$mid+1 && $j!=$end+1)
  {
    if($arr[$i] >= $arr[$j]){
      $temparr[$k++] = $arr[$j++];
    }
    else{
      $temparr[$k++] = $arr[$i++];
    }
  }
  //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
  while($i != $mid+1){
    $temparr[$k++] = $arr[$i++];
  }
  //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
  while($j != $end+1){
    $temparr[$k++] = $arr[$j++];
  }
  for($i=$start; $i<=$end; $i++){
    $arr[$i] = $temparr[$i];
  }
}

À ce stade, notre algorithme de fusion est terminé. Essayons d'appeler :

$arr = array(9,1,5,8,3,7,4,6,2);
MergeSort($arr);
var_dump($arr);

Résultat en cours d'exécution :

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

Analyse de la complexité :

Étant donné que l'algorithme de fusion regroupera et comparera, que la séquence d'origine soit ordonnée ou non, son meilleur, son pire et son temps moyen. La complexité est tout

O(nlogn).

L'algorithme de fusion est un algorithme de tri stable.

Cet article est référencé à partir de "Dahua Data Structure". Il n'est enregistré ici que pour référence future.

Recommandations associées :

Algorithme de tri PHP Bubble Sort (Tri à bulles)

Algorithme de tri PHP Tri par sélection simple (Tri par sélection simple)

Algorithme de tri PHP Tri par insertion directe (Tri par insertion directe)

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!