​PHP Array – Comment utiliser le tri par fusion ?

Nous en savons beaucoup sur les tableaux en PHP. Je ne sais pas ce que vous savez sur le tri par fusion. Je pense qu'un grand nombre de personnes ne connaissent pas cette partie des connaissances. L'article vous mènera à une compréhension plus approfondie pour comprendre ce contenu.

Recommandations associées : Quel est l'algorithme de recherche dans les tableaux PHP ? Comment le trouver ?

Tri par fusion :

Le tri par fusion (ERGE-SOQfT) est un algorithme de tri efficace basé sur l'opération de fusion. L'algorithme utilise une application très typique de. Diviser et conquérir. 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. Prenons comme exemple le code :

<?php
//PHP数组排序算法:合并算法.
//二路归并
$arr1 = array(1,3,5);
$arr2 = array(2,4,6);
//取出一个空数组用于归并空间
$arr3 = array();
while(count($arr1) & count($arr2)){
//只要$arr1和$arr2里面还有元素，就进行循环
//取出每个数组的第-一个元素:进行比较
$arr3[] = $arr1[0] < $arr2[0] ? array_shift($arr1) : array_shift($arr2);
}
//合并结果
print_r(array_merge($arr3 ,$arr1,$arr2));

Le résultat est le suivant :

L'algorithme de tri par fusion est :

1 ) divise le tableau en deux tableaux. .

2) Répétez l'étape 1 pour diviser le tableau en unités les plus petites. .

3) 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.

4) Définissez deux pointeurs, les positions initiales sont les positions de départ des deux séquences triées. .

5) 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 pointeur vers la position suivante.

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

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

Le code est le suivant :

$arr = array(4,7,2,1,5,9,3);
//归并排序函数
function merge_sort($arr){
//递归出口
$len = count($arr);
if($len <= 1) return $arr;
//拆分.
$middle = floor($len / 2);
$left = array_slice($arr,0, $middle);
$right = array_slice($arr, $midd1e);
//假设左边和右边都已经排好序:二路归并
$m = array();
while(count($left) && count($right)){
//只要$arr1和$arr2里面还有元素，就进行循环
//取出每个数组的第一个元素: 进行比较
$arr3[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right);
}
//返回结果
return array_merge($m, $left ,$right);
}
print_r(merge_sort($arr));

Apprentissage recommandé : "Tutoriel vidéo 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!