Implémentation du tri rapide php

Le tri rapide est un algorithme de tri courant et s'exécute plus rapidement que les autres algorithmes de tri dans la plupart des cas, en particulier pour les scénarios de tri de données à grande échelle. L'implémentation du tri rapide en PHP est également très simple et ne nécessite que quelques lignes de code. Cet article présentera l'implémentation du tri rapide en php.

Qu'est-ce que le tri rapide

Le tri rapide est un algorithme de tri basé sur diviser pour régner, qui divise la séquence à trier en plusieurs sous-séquences, et chaque sous-séquence est basée sur un Les valeurs de référence sont triées. La valeur de base peut être n'importe quel nombre, généralement le premier ou le dernier élément est pris, puis les données sont divisées en deux groupes, un côté est supérieur à la valeur de base et l'autre côté est inférieur à la valeur de base. En appelant ce processus de manière récursive et en fusionnant finalement les sous-séquences, une séquence ordonnée peut être obtenue.

implémentation du tri rapide php

Le code est le suivant :

function quickSort($arr)
{
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    $left = $right = array();
    $pivot = $arr[0];
    for ($i = 1; $i < $length; $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    return array_merge(quickSort($left), array($pivot), quickSort($right));
}

Dans le code ci-dessus, $arr est le tableau à trier, $ left et Le tableau $right est utilisé pour stocker respectivement des nombres plus petits et plus grands que la valeur de base, $pivot est la valeur de base et les nombres du tableau sont divisés en deux catégories en fonction de la taille via une boucle, et enfin les nombres dans les parties gauche et droite sont combinées.

La complexité temporelle du tri rapide est O(nlogn), et il est également très efficace en utilisation réelle.

Summary

Le tri rapide est un algorithme de tri courant basé sur diviser pour mieux régner. En sélectionnant le numéro de base, le tableau à trier est divisé en deux sous-séquences et associe récursivement les sous-séquences. sous-séquences. La séquence est triée, et enfin les deux sous-séquences sont fusionnées en une séquence ordonnée. Il est également très simple d'implémenter le tri rapide en PHP. Le code donné ci-dessus est à titre de référence. La complexité temporelle de l'algorithme de tri rapide est O(nlogn) et il fonctionne bien en utilisation réelle.

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!