Explication détaillée de l'algorithme de tri par base en PHP

Explication détaillée de l'algorithme de tri par base en PHP

Le tri par base est un algorithme de tri relativement stable et efficace, qui convient au tri des nombres. Dans le cas de gros volumes de données, le tri par base est plus efficace que les autres algorithmes de tri. Cet article présentera en détail l'algorithme de tri par base en PHP et montrera le processus de mise en œuvre de l'algorithme à travers des exemples de code.

L'idée principale du tri par base est de trier les nombres en fonction du nombre de chiffres. Tout d’abord, en commençant par le chiffre le plus bas, triez tous les nombres par chiffre unique ; puis triez par dizaines de chiffres et ainsi de suite jusqu’à ce que le chiffre le plus élevé soit trié. Chaque tour de tri distribue les numéros dans les seaux correspondants jusqu'à ce que le tour final de tri soit terminé.

Ce qui suit est un exemple d'algorithme de tri de base basé sur PHP :

function radixSort($array) {
    // 获取最大值
    $max = max($array);
    
    // 获取最大值的位数
    $numDigits = strlen((string) $max);
    
    // 创建桶数组
    $buckets = array_fill(0, 10, []);
    
    for ($i = 0; $i < $numDigits; $i++) {
        // 将数字分配到桶中
        foreach ($array as $num) {
            $digit = floor($num / pow(10, $i)) % 10;
            $buckets[$digit][] = $num;
        }
        
        // 将数字从桶中取出，并按顺序放回原数组
        $array = [];
        for ($j = 0; $j < 10; $j++) {
            foreach ($buckets[$j] as $num) {
                $array[] = $num;
            }
            $buckets[$j] = [];
        }
    }
    
    return $array;
}

// 测试排序算法
$array = [23, 6, 78, 12, 456, 2, 56, 11];
$result = radixSort($array);

echo "排序前：";
print_r($array);

echo "排序后：";
print_r($result);

Dans le code ci-dessus, obtenez d'abord la valeur maximale dans le tableau donné et calculez le nombre de chiffres dans la valeur maximale. Créez ensuite un tableau de 10 compartiments pour stocker les numéros attribués en chiffres. Ensuite, effectuez chaque tour de tri via une boucle. À chaque tour de tri, les nombres du tableau sont parcourus et alloués aux compartiments correspondants en fonction du nombre actuel de chiffres. Une fois le tri terminé, les numéros sont retirés du seau et remis dans l'ordre dans le tableau d'origine. Enfin, le tableau trié est renvoyé.

Utilisez l'exemple de code ci-dessus pour les tests, et les résultats de sortie sont les suivants :

Avant le tri : Array
(

[0] => 23
[1] => 6
[2] => 78
[3] => 12
[4] => 456
[5] => 2
[6] => 56
[7] => 11

)

Après le tri : Array
(

[0] => 2
[1] => 6
[2] => 11
[3] => 12
[4] => 23
[5] => 56
[6] => 78
[7] => 456

)

Comme vous pouvez le voir, le L'algorithme de tri par base trie avec succès le tableau trié par taille numérique.

La complexité temporelle de l'algorithme de tri par base est O(k*n), où k est le nombre maximum de chiffres et n est la longueur du tableau. Le tri Radix a une complexité temporelle inférieure à celle des autres algorithmes de tri. Cependant, l'algorithme de tri par base nécessite un espace supplémentaire pour stocker le tableau de compartiments. Par conséquent, dans le cas de volumes de données importants, l'utilisation de la mémoire doit être prise en compte.

Pour résumer, le tri par base est un algorithme de tri efficace adapté au tri des nombres. En comprenant les principes et le processus de mise en œuvre du tri par base, vous pouvez mieux apprendre et appliquer l'algorithme.

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!