Comment écrire un algorithme de tri par tas en utilisant PHP

Comment écrire un algorithme de tri de tas en utilisant PHP

Le tri par tas est un algorithme de tri efficace. Son idée principale est de construire la séquence à trier dans un tas binaire, puis d'ajuster en continu la structure du tas pour réaliser le tri. Cet article explique comment écrire un algorithme de tri de tas à l'aide de PHP et fournit des exemples de code pour référence.

1. Définition du tas
   Avant de commencer à écrire l'algorithme de tri du tas, vous devez d'abord clarifier la définition et les propriétés du tas. Un tas est un arbre binaire complet avec les propriétés suivantes : pour tout nœud i, les deux conditions suivantes sont remplies :
2. La valeur du nœud parent est toujours supérieure ou égale à la valeur du nœud enfant (tas maximum) ;
3. La valeur du nœud parent est toujours inférieure ou égale à la valeur du nœud enfant (min-heap).
4. Ajustement des opérations de tas
   Pour construire un tas, nous devons comprendre comment effectuer des opérations d'ajustement du tas. L'ajustement du tas est divisé en deux étapes :
5. Partez du dernier nœud non-feuille, comparez tour à tour le nœud avec ses nœuds enfants et échangez la valeur la plus grande (ou la plus petite) avec la position du nœud parent ;
Répétez les étapes ci-dessus jusqu'à ce que la structure de l'ensemble du tas satisfasse aux propriétés du tas.

Ce qui suit est un exemple de fonction d'ajustement du tas implémentée en PHP :

function heapify(&$arr, $n, $i) {
    $largest = $i; // 将当前节点标记为最大值节点
    $l = 2 * $i + 1; // 左子节点
    $r = 2 * $i + 2; // 右子节点

    // 如果左子节点大于根节点
    if ($l < $n && $arr[$l] > $arr[$largest]) {
        $largest = $l;
    }

    // 如果右子节点大于根节点
    if ($r < $n && $arr[$r] > $arr[$largest]) {
        $largest = $r;
    }

    // 如果最大值不等于当前节点，则交换它们的位置
    if ($largest != $i) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $temp;

        // 递归调整交换之后的子树
        heapify($arr, $n, $largest);
    }
}

Algorithme de tri du tas
3. Après avoir défini le tas et l'opération d'ajustement du tas, vous pouvez écrire l'algorithme de tri du tas. Les principales étapes du tri du tas sont les suivantes :
   
Construire un tas maximum : à partir du dernier nœud non-feuille, appelez la fonction d'ajustement du tas dans l'ordre pour construire un tas maximum
4. Tri : Échangez l'élément supérieur (valeur maximale ; ) du tas avec la position du dernier élément, puis diminuez la taille du tas de 1, puis appelez la fonction d'ajustement du tas pour ajuster l'ordre des éléments restants
5. Répétez les étapes ci-dessus jusqu'à ce que la taille du tas soit de 1 ; , auquel moment tous les éléments sont classés par ordre croissant.

Ce qui suit est un exemple de fonction de tri par tas implémentée en PHP :

function heapSort(&$arr) {
    $n = count($arr);

    // 构建最大堆
    for ($i = ($n / 2) - 1; $i >= 0; $i--) {
        heapify($arr, $n, $i);
    }

    // 排序
    for ($i = $n - 1; $i > 0; $i--) {
        // 交换堆顶和最后一个元素
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;

        // 调整剩余元素的顺序
        heapify($arr, $i, 0);
    }
}

Utilisation de l'algorithme de tri par tas
4. L'utilisation de l'algorithme de tri par tas est très simple Il vous suffit de transmettre le tableau à trier en paramètre. la fonction de tri de tas ci-dessus. Voici un exemple de tri d'un tableau à l'aide de l'algorithme de tri par tas :
   

$arr = [3, 7, 2, 11, 1, 9, 6, 4, 8];

echo "排序前：" . implode(", ", $arr) . "
";

heapSort($arr);

echo "排序后：" . implode(", ", $arr) . "
";

En exécutant le code ci-dessus, vous obtiendrez le résultat suivant :

排序前：3, 7, 2, 11, 1, 9, 6, 4, 8
排序后：1, 2, 3, 4, 6, 7, 8, 9, 11

De cette façon, nous avons écrit et appliqué avec succès l'algorithme de tri par tas en utilisant PHP .

Résumé :

Le tri par tas est un algorithme de tri efficace qui implémente le tri en construisant un tas maximum (ou minimum). En ajustant la structure du tas, nous pouvons facilement mettre en œuvre le tri du tas. Écrire un algorithme de tri de tas à l'aide de PHP est relativement simple. Il vous suffit d'écrire une fonction d'ajustement de tas et une fonction de tri de tas, et de transmettre le tableau à trier en tant que paramètre pour effectuer le tri. J'espère que le contenu de cet article pourra vous aider à comprendre et à utiliser l'algorithme de tri par tas.

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!