Apprenez les principes et l'analyse de la complexité temporelle de l'algorithme de tri par comptage en PHP.

Apprenez les principes et l'analyse de la complexité temporelle de l'algorithme de tri par comptage en PHP

Le tri par comptage est un algorithme de tri non comparatif, adapté aux situations où la plage de données est petite et connue. Son idée de base est de compter le nombre d'occurrences de chaque élément, puis de le remplir dans le tableau de sortie afin de réaliser le tri. Cet article présentera les principes, les étapes et l'analyse de la complexité temporelle du tri par comptage, et fournira des exemples de code PHP spécifiques.

1. Principe :
   Le principe du tri par comptage est relativement simple. Supposons que le tableau à trier est un tableau et que la plage d'éléments est [0, k]. Nous devons d'abord créer un tableau de comptage d'une taille de k+1 pour compter le nombre d'occurrences de chaque élément. Lors de l'itération sur le tableau d'origine, les éléments sont comptés et stockés dans le tableau de comptage. Ensuite, nous accumulons séquentiellement les éléments dans le tableau de comptage pour déterminer la position de l'élément dans le tableau de sortie. Enfin, parcourez le tableau d'origine et placez chaque élément dans la position correspondante (selon l'index en nombre) pour terminer le tri.
2. Étapes :
3. Créez un tableau de comptage de taille k+1 et initialisez-le à 0.
4. Parcourez le tableau d'origine, comptez le nombre d'occurrences de chaque élément et stockez-le dans le tableau de comptage.
5. Accumulez le tableau de comptage pour déterminer la position de chaque élément dans le tableau de sortie.
6. Créez un tableau de sortie de la même taille que le tableau d'origine.
7. Parcourez à nouveau le tableau d'origine et placez chaque élément dans le tableau de sortie en fonction de l'index dans le tableau de comptage.
8. La sortie du tableau de sortie est le résultat après comptage et tri.
9. Analyse de la complexité temporelle :
10. La complexité temporelle de la création du tableau de comptage est O(k).
11. La complexité temporelle de la traversée du tableau d'origine et du comptage des occurrences de chaque élément est O(n).
12. La complexité temporelle de l'accumulation du tableau de comptage est O(k).
13. La complexité temporelle de la création du tableau de sortie est O(n).
14. La complexité temporelle du parcours à nouveau du tableau d'origine et du placement des éléments dans le tableau de sortie est O(n).
15. La complexité temporelle totale est O(k) + O(n) + O(k) + O(n) + O(n), qui est simplifiée en O(n + k).

Ce qui suit est un exemple de code d'utilisation du langage PHP pour implémenter l'algorithme de tri par comptage :

function countingSort($array)
{
    $maxValue = max($array);
    $count = array_fill(0, $maxValue + 1, 0);
    $n = count($array);

    foreach ($array as $value) {
        $count[$value]++;
    }

    for ($i = 1; $i <= $maxValue; $i++) {
        $count[$i] += $count[$i - 1];
    }

    $output = array_fill(0, $n, 0);

    for ($i = $n - 1; $i >= 0; $i--) {
        $output[$count[$array[$i]] - 1] = $array[$i];
        $count[$array[$i]]--;
    }

    return $output;
}

$array = [4, 2, 0, 1, 3, 2, 1]; // 待排序数组
$sortedArray = countingSort($array);
print_r($sortedArray);

Ce qui précède est le contenu de l'apprentissage des principes et de l'analyse de la complexité temporelle de l'algorithme de tri par comptage en PHP. J'espère que cela vous aidera à comprendre le tri par comptage.

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!