Apprenez les principes et l'analyse de la complexité temporelle de l'algorithme de tri par tas en PHP.

Apprenez les principes et l'analyse de la complexité temporelle de l'algorithme de tri du tas en PHP

Le tri du tas est un algorithme de tri basé sur la structure des données du tas, et sa complexité temporelle est O(nlogn). Cet article présentera les principes de l'algorithme de tri par tas dans le langage PHP et fournira des exemples de code.

1. La définition et les propriétés d'un tas

Avant d'apprendre le tri par tas, vous devez d'abord comprendre la définition et les propriétés d'un tas. Un tas est un arbre binaire complet dans lequel la valeur de chaque nœud est supérieure ou égale à la valeur de ses nœuds enfants. Nous appelons un tel tas un tas big-max. Au contraire, si la valeur de chaque nœud est inférieure ou égale à la valeur de son nœud enfant, on l'appelle un petit tas supérieur.

En raison des caractéristiques du tas, l'élément supérieur du tas est la valeur maximale ou minimale. Par conséquent, dans le tri du tas, nous considérons généralement le tableau à trier comme un arbre binaire complet et utilisons les caractéristiques du tas pour. tri.

2. Principe de l'algorithme de tri par tas

L'algorithme de tri par tas est principalement divisé en deux étapes : la construction d'un tas et l'ajustement du tas.

1. Build Heap : ajustez le tableau à trier dans un grand tas supérieur.

Les étapes sont les suivantes :

• Voyagez vers l'avant un par un à partir du dernier nœud non-feuille (c'est-à-dire n/2-1), et appelez la fonction d'ajustement du tas (adjustHeap).
• La fonction d'ajustement du tas adopte une approche descendante pour ajuster le nœud actuel et son sous-arbre afin de garantir que le nœud actuel est plus grand que ses nœuds enfants.
• Répétez les deux étapes ci-dessus jusqu'à ce que l'ensemble du tableau soit ajusté en un grand tas supérieur.

2. AdjustHeap : ajustez le nœud actuel et son sous-arbre dans un grand tas supérieur.

Les étapes sont les suivantes :

• Calculez les positions de ses nœuds enfants gauche et droit en fonction de la position du nœud actuel.
• Comparez les valeurs du nœud actuel et de ses nœuds enfants gauche et droit pour trouver la position du plus grand nœud.
• Si la position du nœud maximum n'est pas la position du nœud actuel, échangez les valeurs du nœud maximum et du nœud actuel, et appelez-vous récursivement pour ajuster le sous-arbre échangé.

3. Tri (sortHeap) : échangez l'élément supérieur du tas (c'est-à-dire le premier élément du tableau) avec le dernier nœud feuille, puis effectuez un ajustement du tas sur les n-1 éléments restants.

Les étapes sont les suivantes :

• Échangez l'élément supérieur du tas avec le dernier nœud feuille.
• Réduisez la portée du tas, c'est-à-dire ignorez le dernier nœud feuille qui a été trié.
• Ajustements du tas à plage réduite pour conserver la nature du grand tas supérieur.
• Répétez les trois étapes ci-dessus jusqu'à ce que la plage du tas soit réduite à 1.

3. Exemple de code PHP

Ce qui suit est un exemple de code pour implémenter l'algorithme de tri du tas en langage PHP :

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

    // 构建大顶堆
    for ($i = floor($length/2 - 1); $i >= 0; $i--) {
        adjustHeap($arr, $i, $length);
    }

    // 调整堆并排序
    for ($i = $length - 1; $i >= 0; $i--) {
        // 交换堆顶元素和最后一个叶子节点
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;

        // 调整堆使其保持大顶堆性质
        adjustHeap($arr, 0, $i);
    }
}

function adjustHeap(&$arr, $i, $length) {
    $largest = $i; // 最大值的位置
    $left = $i * 2 + 1; // 左子节点的位置
    $right = $i * 2 + 2; // 右子节点的位置

    // 比较当前节点与左右子节点的值，找到最大值的位置
    if ($left < $length && $arr[$left] > $arr[$largest]) {
        $largest = $left;
    }
    if ($right < $length && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }

    // 如果最大值的位置不是当前节点的位置，则交换两个位置的值，并递归调整堆
    if ($largest != $i) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $temp;
        adjustHeap($arr, $largest, $length);
    }
}

// 测试
$arr = [8, 3, 6, 2, 9, 1];
heapSort($arr);
print_r($arr); // 输出 [1, 2, 3, 6, 8, 9]

4. Analyse de la complexité temporelle

La complexité temporelle du tri du tas est O(nlogn). Parmi eux, la complexité temporelle de la construction du tas est O(n), et la complexité temporelle de l'ajustement du tas est O(logn). Puisque n éléments doivent être triés, la complexité temporelle totale est O(nlogn).

Résumé

Cet article présente en détail les principes de l'algorithme de tri par tas dans le langage PHP et fournit des exemples de code correspondants. Le tri par tas est un algorithme de tri efficace adapté aux grands tableaux à trier. En apprenant l'algorithme de tri par tas, vous pouvez améliorer encore votre compréhension et vos capacités d'application des structures de données et des algorithmes.

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!