Étapes de mise en œuvre et analyse de la complexité temporelle de l'algorithme de tri de base en PHP.

Étapes de mise en œuvre et analyse de la complexité temporelle de l'algorithme de tri par base en PHP

Radix Sort est un algorithme de tri à complexité temporelle linéaire (O(n)) couramment utilisé, qui utilise des éléments de comparaison et d'allocation bit par bit pour réaliser le tri. . Dans cet article, nous présenterons les étapes de mise en œuvre de l'algorithme de tri par base et analyserons sa complexité temporelle.

L'idée de base du tri par base est d'attribuer tous les éléments à comparer (entiers positifs) à un nombre limité de buckets, puis de collecter tour à tour les éléments dans chaque bucket pour enfin terminer le tri.

Les étapes de mise en œuvre sont les suivantes :

1. Initialiser le tableau de buckets : Créez un tableau bidimensionnel pour représenter les buckets, chaque bucket est un tableau unidimensionnel. Le nombre de compartiments est déterminé par le nombre maximum de chiffres d'éléments à trier.
2. Trouver le nombre maximum de chiffres : parcourez le tableau à trier, trouvez le plus grand élément et déterminez son nombre de chiffres.
3. Distribuez et collectez petit à petit : du bit bas au bit haut, retirez tour à tour la valeur du nombre de bits correspondant de chaque élément, et allouez les éléments aux buckets correspondants. Ensuite, récupérez-les dans le tableau d'origine dans l'ordre des compartiments.
4. Répétez l'étape 3 : allouez et collectez les bits les plus élevés dans l'ordre jusqu'à ce que le bit le plus élevé soit alloué.
5. Tri complet : après plusieurs allocations et collections, le tableau à trier est devenu ordonné.

Ce qui suit est un exemple de code PHP pour le tri par base :

function radixSort(array $arr): array {
    // 找到待排序数组的最大值
    $max = max($arr);
    
    // 确定最大值的位数
    $maxDigit = strlen((string)$max);
    
    // 初始化桶数组
    $buckets = [];
    for ($i = 0; $i < 10; $i++) {
        $buckets[$i] = [];
    }
    
    // 依次按位进行分配和收集
    for ($digit = 1; $digit <= $maxDigit; $digit++) {
        // 分配到桶中
        foreach ($arr as $num) {
            $index = ($num / pow(10, $digit - 1)) % 10;
            array_push($buckets[$index], $num);
        }
        
        // 按照桶的顺序进行收集
        $pos = 0;
        for ($i = 0; $i < 10; $i++) {
            while (!empty($buckets[$i])) {
                $arr[$pos] = array_shift($buckets[$i]);
                $pos++;
            }
        }
    }
    
    return $arr;
}

// 测试
$arr = [170, 45, 75, 90, 802, 24, 2, 66];
$result = radixSort($arr);
print_r($result);

Analyse de la complexité temporelle :

• Si le nombre de chiffres des éléments à trier est d et le nombre de compartiments est k, alors la complexité temporelle de le tri de base est O(d * (n + k)).
• Dans le pire des cas, le nombre de bits d'éléments à trier est égal au nombre de buckets, c'est-à-dire d = k, et la complexité temporelle est O(2 * n).
• Dans des circonstances moyennes, le nombre de chiffres des éléments à trier n'a rien à voir avec le nombre de compartiments, c'est-à-dire d

Bien que le tri par base puisse atteindre une complexité temporelle linéaire, il a une complexité spatiale élevée et nécessite des tableaux de compartiments supplémentaires pour stocker les éléments. De plus, dans le cas de nombres négatifs, des opérations de conversion et d'inversion sont également nécessaires sur les éléments. Cependant, dans les applications pratiques, si les données à trier sont petites ou si l’environnement dispose de suffisamment de mémoire, le tri par base reste un algorithme de tri efficace.

En résumé, cet article présente les étapes d'implémentation de l'algorithme de tri radix en PHP et analyse sa complexité temporelle. En comparant et en attribuant des éléments petit à petit, le tri par base peut effectuer la tâche de tri efficacement. Lors de la rédaction d'applications pratiques, vous pouvez choisir un algorithme de tri approprié en fonction des caractéristiques des éléments à trier pour améliorer les performances.

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!