Analyse de la complexité de divers algorithmes de tri de tableaux PHP

Complexité de l'algorithme de tri de tableau PHP : Tri à bulles : O(n^2) Tri rapide : O(n log n) (moyenne) Tri par fusion : O(n log n)

Algorithme de tri de tableau PHP Analyse de complexité

En PHP, il existe plusieurs algorithmes de tri qui peuvent être utilisés pour trier les éléments d'un tableau. L'efficacité de chaque algorithme varie en fonction de la taille du tableau et de la distribution des données.

Tri à bulles

Le tri à bulles est un algorithme de tri simple, mais il est moins efficace. Cela fonctionne en comparant à plusieurs reprises les éléments adjacents et en échangeant le plus grand élément à la fin du tableau.

function bubbleSort($arr) {
    for ($i = 0; $i < count($arr); $i++) {
        for ($j = 0; $j < count($arr) - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

Complexité temporelle : O(n^2)

Tri rapide

Le tri rapide est un algorithme diviser pour régner et est généralement considéré comme l'algorithme de tri le plus efficace. Il utilise la récursion pour diviser le tableau en sous-tableaux plus petits et trier chaque sous-tableau.

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

Complexité temporelle : O(n log n) (en moyenne)

Tri par fusion

Le tri par fusion est également un algorithme diviser pour régner. Cela fonctionne en divisant récursivement le tableau en sous-tableaux plus petits, en triant les sous-tableaux, puis en fusionnant les sous-tableaux triés.

function mergeSort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }
    $mid = count($arr) / 2;
    $left = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));
    return merge($left, $right);
}
function merge($left, $right) {
    $merged = [];
    $i = $j = 0;
    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] <= $right[$j]) {
            $merged[] = $left[$i];
            $i++;
        } else {
            $merged[] = $right[$j];
            $j++;
        }
    }
    return array_merge($merged, array_slice($left, $i), array_slice($right, $j));
}

Complexité temporelle : O(n log n)

Cas pratique

Supposons que vous ayez un tableau contenant 10 000 entiers. Vous pouvez trier ce tableau en utilisant l'algorithme ci-dessus et mesurer le temps nécessaire au tri à l'aide de la fonction microtime() de PHP.

$arr = range(1, 10000);
shuffle($arr); // 打乱数组以获得更现实的结果

$timeStart = microtime(true);
bubbleSort($arr);
$timeEnd = microtime(true);
echo "Bubble Sort: " . ($timeEnd - $timeStart) . " 秒\n";

$timeStart = microtime(true);
quickSort($arr);
$timeEnd = microtime(true);
echo "Quick Sort: " . ($timeEnd - $timeStart) . " 秒\n";

$timeStart = microtime(true);
mergeSort($arr);
$timeEnd = microtime(true);
echo "Merge Sort: " . ($timeEnd - $timeStart) . " 秒\n";

Pour un tableau de 10 000 entiers, les résultats sont les suivants :

Bubble Sort: 1.0129920272827 秒
Quick Sort: 0.001443982124329 秒
Merge Sort: 0.001151084899902 秒

Les résultats montrent que le tri rapide et le tri par fusion sont nettement plus efficaces que le tri à bulles.

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!