Principe de mise en œuvre de l'algorithme de tri par comptage en PHP

Principe d'implémentation de l'algorithme de tri par comptage en PHP

Le tri par comptage est un algorithme de tri non comparatif. Son idée de base est de compter les occurrences de chaque élément puis de le placer dans une position ordonnée en fonction de la taille de l'élément. Le tri par comptage convient aux situations où la plage d'éléments est petite et où il existe de nombreux éléments répétés. La complexité temporelle est O(n), et il s'agit d'un algorithme de tri efficace.

Principe de mise en œuvre :

1. Tout d'abord, parcourez le tableau à trier et trouvez les valeurs maximales et minimales pour déterminer la taille du tableau de comptage.
2. Créez un tableau de comptage dont la longueur est la différence entre la valeur maximale et la valeur minimale plus 1, et initialisez-le à 0.
3. Parcourez à nouveau le tableau à trier, comptez le nombre d'occurrences de chaque élément et enregistrez le nombre dans le tableau de comptage.
4. Effectuez une opération d'accumulation sur le tableau de comptage, c'est-à-dire additionnez l'élément à la position actuelle et l'élément à la position précédente.
5. Créez un tableau temporaire de la même longueur que le tableau à trier pour stocker les résultats du tri.
6. Parcourez le tableau à trier d'arrière en avant et utilisez la valeur accumulée dans le tableau de comptage pour placer les éléments aux positions correspondantes dans le tableau temporaire.
7. Copiez les éléments du tableau temporaire dans le tableau d'origine pour terminer le tri.

Ce qui suit est un exemple de code PHP :

function countSort($arr) {
    $min = min($arr); // 寻找最小值
    $max = max($arr); // 寻找最大值
    $count = array_fill($min, $max - $min + 1, 0); // 创建计数数组

    foreach ($arr as $num) {
        $count[$num]++; // 统计每个元素的出现次数
    }

    for ($i = $min + 1; $i <= $max; $i++) {
        $count[$i] += $count[$i - 1]; // 计算累加值
    }

    $temp = array_fill(0, count($arr), 0); // 创建临时数组

    for ($i = count($arr) - 1; $i >= 0; $i--) {
        $temp[--$count[$arr[$i]]] = $arr[$i]; // 将元素放置到临时数组中的相应位置上
    }

    for ($i = 0; $i < count($arr); $i++) {
        $arr[$i] = $temp[$i]; // 将临时数组中的元素复制到原始数组中
    }

    return $arr;
}

// 测试示例
$arr = [8, 3, 5, 4, 7, 6, 1, 6, 4, 4];
$result = countSort($arr);
echo implode(' ', $result); // 输出：1 3 4 4 4 5 6 6 7 8

Ce qui précède est le principe d'implémentation de l'algorithme de tri par comptage en PHP en comptant le nombre d'occurrences de chaque élément, puis en plaçant les éléments dans une position ordonnée en fonction du. numéro, le tableau trié est implémenté le tri. Cet algorithme convient aux situations où la gamme d'éléments est petite et où il y a de nombreux éléments répétés, et l'opération de tri peut être effectuée dans un temps plus court.

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!