Introduction au principe et au code d'implémentation de l'algorithme de tri rapide PHP

Le contenu de cet article concerne les principes et l'introduction du code de l'algorithme de tri rapide PHP. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Principe de l'algorithme

Les animations suivantes sont tirées de l'algorithme de cinq minutes, démontrant les principes et les étapes de l'algorithme de tri rapide.

Étapes :

• Sélectionnez une valeur de référence dans le tableau
• Définissez une valeur de tableau plus grande que la valeur de référence Placez ceux du même côté et placez ceux qui sont plus petits que la valeur de référence de l'autre côté. La valeur de référence est au milieu
• Triez récursivement les tableaux des deux côtés de la colonne<.>

Mise en œuvre du code

function quickSort($arr)
{
    $len = count($arr);
    if ($len  $v) {
            $up[] = $arr[$i];
        } else {
            $low[] = $arr[$i];
        }
    }
    $low = quickSort($low);
    $up = quickSort($up);

    return array_merge($low, array($v), $up);
}

Code du test :

$startTime = microtime(1);

$arr = range(1, 10);
shuffle($arr);

echo "before sort: ", implode(', ', $arr), "\n";
$sortArr = quickSort($arr);
echo "after sort: ", implode(', ', $sortArr), "\n";

echo "use time: ", microtime(1) - $startTime, "s\n";

Résultat du test :

before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8
after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
use time: 0.0009009838104248s

Heure complexité

La complexité temporelle du tri rapide est Le pire des cas est O(N2), et la complexité temporelle moyenne est O(N*lgN).

Cette phrase est facile à comprendre : Supposons qu'il y ait N nombres dans la séquence à trier. La complexité temporelle d’un parcours est O(N). Combien de fois devons-nous le parcourir ? Au moins lg(N+1) fois et au plus N fois.

1) Pourquoi est-ce au moins lg(N+1) fois ? Le tri rapide utilise la méthode diviser pour régner. Nous le considérons comme un arbre binaire. Le nombre de fois qu'il doit être parcouru est la profondeur de l'arbre binaire. Selon la définition d'un arbre binaire complet, sa profondeur. est au moins lg(N+1). Par conséquent, le nombre d’itérations du tri rapide est d’au moins lg(N+1) fois.

2) Pourquoi c'est jusqu'à N fois ? Cela devrait être très simple. Considérez le tri rapide comme un arbre binaire avec une profondeur maximale de N. Par conséquent, le nombre de parcours pour le tri à lecture rapide est au plus N fois.

[Recommandations associées :

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!