Implémentation de l'algorithme de tri par comptage PHP (exemple de code)

Le tri par comptage est un algorithme permettant de trier un ensemble d'objets basé sur de petites clés entières ; c'est-à-dire qu'il s'agit d'un algorithme de tri d'entiers. Il détermine la position de chaque valeur clé dans la séquence de sortie en comptant le nombre d'objets avec des valeurs clés différentes et en utilisant l'arithmétique sur ces nombres.

Le tri par comptage ne peut être utilisé que lorsque le changement de clé n'est pas supérieur au nombre total d'éléments. Il est souvent utilisé comme sous-programme d'un autre algorithme de tri (tri par base), qui peut gérer efficacement des clés plus volumineuses.

En bref, le tri par comptage est un algorithme de tri temporel linéaire stable. Le tri par comptage utilise un tableau supplémentaire C, où le i-ième élément est le nombre d'éléments dont la valeur est égale à i dans le tableau A à trier. Disposez ensuite les éléments de A dans la position correcte selon le tableau C.

Les étapes habituelles de mise en œuvre de l'algorithme de tri par comptage sont :

1. Trouver les éléments les plus grands et les plus petits du tableau à trier ; 2 .Comptez le nombre d'occurrences de chaque élément de valeur i dans le tableau et stockez-le dans le i-ème élément du tableau C

3. chacun Ajoutez l'élément à l'élément précédent);

4. Remplissez le tableau cible à l'envers : placez chaque élément i dans le C[i]-ième élément du nouveau tableau et ajoutez C[i] chacun. heure à laquelle un élément est placé. Soustraire 1.

<?php
function counting_sort($my_array, $min, $max)
{
    $count = array();
    for($i = $min; $i <= $max; $i++)
    {
        $count[$i] = 0;
    }

    foreach($my_array as $number)
    {
        $count[$number]++;
    }
    $z = 0;
    for($i = $min; $i <= $max; $i++) {
        while( $count[$i]-- > 0 ) {
            $my_array[$z++] = $i;
        }
    }
    return $my_array;
}
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "原始数组 :\n";
echo implode(&#39;, &#39;,$test_array );
echo "\n排序后数组\n:";
echo implode(&#39;, &#39;,counting_sort($test_array, -1, 5)). PHP_EOL;

原始数组 : 3, 0, 2, 5, -1, 4, 1 
排序后数组 :-1, 0, 1, 2, 3, 4, 5

》Cet article concerne la méthode d'implémentation de l'algorithme de tri par comptage PHP. J'espère qu'il sera utile aux amis dans le besoin !

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!