Tri rapide du tableau PHP par rapport au tri par fusion

Le tri rapide est un algorithme récursif qui divise le tableau en éléments plus petits et en éléments plus grands et les trie de manière récursive, tandis que le tri par fusion divise récursivement le tableau en tableaux plus petits, trie chaque petit tableau, puis le fusionne à nouveau dans le tableau d'origine. Les codes implémentés par PHP sont : Tri rapide : divisez le tableau en éléments plus petits et plus grands que la valeur de base, puis triez chaque partie de manière récursive. Tri par fusion : divisez récursivement un tableau en tableaux plus petits, triez chaque tableau plus petit, puis fusionnez les petits tableaux triés dans le tableau d'origine.

Tri rapide de tableau PHP vs tri par fusion

Qu'est-ce que le tri rapide et le tri par fusion ?

Le tri rapide et le tri par fusion sont deux algorithmes courants utilisés pour trier les tableaux.

• Tri rapide : Divisez le tableau en deux parties, l'une contenant des éléments plus petits et l'autre contenant des éléments plus grands, puis triez chaque partie de manière récursive.
• Tri par fusion : Divisez le tableau de manière récursive en tableaux plus petits, triez chaque tableau plus petit, puis fusionnez les tableaux plus petits triés dans le tableau d'origine.

Implémentation du code 是 Ce qui suit est une fonction de tri de décharge et de fusion rapide implémentée avec PHP :

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

Tri par fusion :

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

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

cas de combat réel

Considération d'un Ar désordonné rayon d'entiers .

$sortedArray = quickSort([5, 2, 8, 3, 1, 9, 4, 7, 6]);
print_r($sortedArray);

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Utilisation du tri par fusion :

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

Sortie :

[1, 2, 3, 4, 5, 6, 7, 8, 9]

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!