Exemple de code PHP pour un tri rapide

Le contenu de cet article concerne l'exemple de code de tri rapide en PHP. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Tri rapide

Tri rapide (anglais : Quicksort), également connu sous le nom de tri par échange de partition, abréviation de tri rapide, un algorithme de tri, proposé pour la première fois par Tony Hall. En moyenne, le tri de n éléments nécessite des comparaisons O(n log n). Dans le pire des cas, des comparaisons O(n2) sont nécessaires, mais cela est rare. En fait, le tri rapide O(n log n) est souvent beaucoup plus rapide que les autres algorithmes car sa boucle interne peut être réalisée efficacement sur la plupart des architectures.

Les étapes sont :

Choisissez un élément de la séquence, appelé le "pivot",

Réorganisez la séquence, tous les ratios Éléments avec des valeurs de base plus petites sont placées devant la base, et tous les éléments avec des valeurs plus grandes que la base sont placés après la base (le même nombre peut aller des deux côtés). Après cette partition, la donnée se trouve au milieu de la séquence. C'est ce qu'on appelle une opération de partition.

Trier récursivement le sous-tableau d'éléments plus petits que la valeur de base et le sous-tableau d'éléments supérieurs à la valeur de base.

Lorsque la récursion atteint le bas, la taille du tableau est zéro ou un, ce qui signifie qu'il a été trié. Cet algorithme prendra définitivement fin, car à chaque itération, il déplacera au moins un élément vers sa position finale.

Introduction dans Wikipédia. L'idée principale est d'utiliser la récursion. L'animation ci-dessous est très vivante.

Démonstration d'animation

Exemple

<?php $arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];

function quickSort($arr)
{
    $count = count($arr);

    if ($count < 2) {
        return $arr;
    }

    $leftArray = $rightArray = array();
    $middle = $arr[0];// 基准值

    for ($i = 1; $i < $count; $i++) {
        // 小于基准值，存入左边；大于基准值，存入右边
        if ($arr[$i] < $middle) {
            $leftArray[] = $arr[$i];
        } else {
            $rightArray[] = $arr[$i];
        }
    }

    $leftArray = quickSort($leftArray);
    $rightArray = quickSort($rightArray);

    return array_merge($leftArray, array($middle), $rightArray);
    // 倒序
    // return array_merge($rightArray, array($middle), $leftArray);
}

print_r(quickSort($arr));
// Array ( [0] => 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33

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!