Analyse de la complexité de divers algorithmes de tri de tableaux PHP-tutoriel php-php.cn

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

王林

Libérer： 2024-04-27 09:03:02

original

806 Les gens l'ont consulté

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)

各种 PHP 数组排序算法的复杂度分析

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;
}

Copier après la connexion

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));
}

Copier après la connexion

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));
}

Copier après la connexion

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";

Copier après la connexion

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 秒

Copier après la connexion

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!