Maison >développement back-end >tutoriel php >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 :
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!