Comment implémenter un algorithme de tri par bucket avec PHP

Comment implémenter un algorithme de tri par bucket avec PHP

Le tri par bucket est un algorithme de tri avec une complexité temporelle linéaire, qui convient aux situations où la plage de tri est relativement étroite. Son idée de base est de diviser les éléments à trier en un nombre limité de buckets, puis de trier les éléments dans chaque bucket, et enfin de fusionner les éléments de chaque bucket dans l'ordre.

En PHP, nous pouvons implémenter l'algorithme de tri par bucket via des tableaux. Voici un exemple de code pour le tri des buckets en PHP :

<?php
function bucketSort(array $arr)
{
    // 找出最大值和最小值
    $min = min($arr);
    $max = max($arr);

    // 桶的数量，这里假设为10
    $bucketCount = 10;

    // 计算每个桶的容量
    $bucketSize = ceil(($max - $min + 1) / $bucketCount);

    // 创建桶
    $buckets = array_fill(0, $bucketCount, []);

    // 将元素放入桶中
    foreach ($arr as $num) {
        $bucketIndex = floor(($num - $min) / $bucketSize);
        array_push($buckets[$bucketIndex], $num);
    }

    // 对每个桶进行排序
    foreach ($buckets as &$bucket) {
        sort($bucket);
    }

    // 合并各个桶中的元素
    $sortedArr = [];
    foreach ($buckets as $bucket) {
        $sortedArr = array_merge($sortedArr, $bucket);
    }

    return $sortedArr;
}

// 测试
$arr = [5, 2, 8, 9, 1, 3, 7, 6, 4];
$sortedArr = bucketSort($arr);
echo "排序前: " . implode(', ', $arr) . "
";
echo "排序后: " . implode(', ', $sortedArr) . "
";
?>

Dans le code ci-dessus, nous trouvons d'abord les valeurs maximales et minimales dans le tableau à trier, puis calculons la capacité de chaque bucket. Après avoir créé le tableau de compartiments vide, nous parcourons le tableau à trier et plaçons chaque élément dans le compartiment correspondant en fonction de la valeur de l'élément. Ensuite, les éléments de chaque compartiment sont triés. Enfin, nous combinons les éléments de chaque compartiment afin d'obtenir le tableau trié.

10 seaux sont utilisés dans l'exemple de code ci-dessus, vous pouvez ajuster le nombre de seaux en fonction de la situation réelle. L'algorithme de tri par compartiments a certaines exigences concernant la plage de valeurs du tableau à trier. Si la plage de valeurs est trop grande, cela peut entraîner un trop grand nombre ou un nombre insuffisant de compartiments, affectant ainsi l'efficacité de l'algorithme. Par conséquent, dans les applications pratiques, le nombre et la capacité des godets doivent être raisonnablement définis en fonction de problèmes spécifiques.

J'espère qu'à travers l'introduction et l'exemple de code de cet article, vous pourrez comprendre l'idée de base de l'algorithme de tri des buckets et implémenter une fonction de tri des buckets efficace en utilisant PHP.

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!