Comment utiliser la méthode diviser pour régner pour implémenter l'algorithme de tri par fusion en PHP et améliorer l'efficacité du tri ?

Comment utiliser la méthode diviser pour régner pour implémenter l'algorithme de tri par fusion en PHP et améliorer l'efficacité du tri ?

Le tri par fusion est un algorithme de tri efficace. Il utilise l'idée de la méthode diviser pour régner pour diviser le tableau à trier en deux parties, trier les deux sous-tableaux respectivement, puis fusionner les deux sous-tableaux triés en deux. Un tableau ordonné. Le tri par fusion peut transformer de manière stable un tableau non trié en un tableau ordonné en divisant continuellement le problème en sous-problèmes plus petits et en combinant les solutions aux sous-problèmes.

En PHP, pour implémenter l'algorithme de tri par fusion et améliorer l'efficacité du tri, vous pouvez suivre les étapes suivantes :

1. Écrivez une fonction nommée mergeSort comme fonction d'entrée, qui accepte un tableau à trier en paramètre.

function mergeSort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }
    $mid = floor(count($arr) / 2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);
    $left = mergeSort($left);
    $right = mergeSort($right);
    return merge($left, $right);
}

2. Définissez une fonction appelée fusion, qui est utilisée pour fusionner deux sous-tableaux triés.

function merge($left, $right) {
    $result = [];
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }
    while (count($left) > 0) {
        $result[] = array_shift($left);
    }
    while (count($right) > 0) {
        $result[] = array_shift($right);
    }
    return $result;
}

Dans la fonction mergeSort, déterminez d'abord si la longueur du tableau est inférieure ou égale à 1. Si tel est le cas, le tableau d'origine est renvoyé directement sans tri. Sinon, divisez le tableau en deux sous-tableaux et appelez la fonction mergeSort pour trier les sous-tableaux respectivement. Enfin, la fonction de fusion est appelée pour fusionner les deux sous-tableaux triés en un tableau ordonné.

Dans la fonction de fusion, deux boucles while sont utilisées pour supprimer séquentiellement les éléments les plus petits des deux sous-tableaux et les ajouter au tableau de résultats $result jusqu'à ce que l'un des sous-tableaux soit vide. Ensuite, ajoutez les éléments des sous-tableaux restants au tableau de résultats dans l'ordre. Enfin, le tableau résultat est renvoyé.

Grâce aux étapes ci-dessus, nous pouvons utiliser la méthode diviser pour régner pour implémenter l'algorithme de tri par fusion en PHP, et puisque la complexité temporelle du tri par fusion est O(nlogn), l'efficacité du tri peut être améliorée dans le cas de grandes quantités. de données.

L'exemple de code est le suivant :

$arr = [5, 3, 8, 6, 2, 9, 1, 7, 4];
$sortedArr = mergeSort($arr);
print_r($sortedArr);

Le résultat de sortie est : [1, 2, 3, 4, 5, 6, 7, 8, 9]

Ce qui précède explique comment utiliser la méthode diviser pour régner pour implémentez l'algorithme de tri par fusion en PHP et améliorez le tri. Méthodes efficaces et exemples de code. En apprenant et en comprenant les idées et la mise en œuvre de l'algorithme de tri par fusion, nous pouvons mieux appliquer et maîtriser d'autres algorithmes diviser pour régner et améliorer notre efficacité dans la résolution des problèmes.

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!