Comprendre les principes et la mise en œuvre de l'algorithme de tri par tas en PHP ?

Comprendre les principes et la mise en œuvre de l'algorithme de tri par tas en PHP ?

En informatique, Heap Sort est un algorithme de tri efficace qui utilise les caractéristiques de la structure de données du tas binaire. Le tri par tas peut trier un tableau non ordonné en un tableau ordonné avec une complexité temporelle O(nlogn).

Le principe du tri par tas est de réaliser le tri en construisant un tas maximum (ou tas minimum). Le tas maximum signifie que la valeur clé du nœud parent est toujours supérieure (ou égale) à la valeur clé de son nœud enfant, et l'inverse est vrai pour le tas minimum. Les étapes du tri par tas sont les suivantes :

1. Construire un tas max : Construisez le tableau non ordonné dans un tas max de telle sorte que la valeur de chaque nœud parent soit supérieure (ou égale) à la valeur de son nœud enfant. L'opération spécifique consiste à partir du dernier nœud non-feuille, à effectuer une opération « puits » sur chaque nœud et à l'échanger avec ses nœuds enfants jusqu'à ce que l'exigence maximale du tas soit satisfaite.
2. Échanger et ajuster : échangez le nœud racine du tas max (c'est-à-dire le premier élément du tableau) avec le dernier élément, c'est-à-dire mettez la valeur maximale en dernière position. Ensuite, les n-1 premiers éléments restants sont redimensionnés en un tas maximum.
3. Répétez l'étape 2 jusqu'à ce que tous les éléments soient triés.

Ce qui suit est un exemple de code qui utilise PHP pour implémenter l'algorithme de tri par tas :

// 堆排序
function heapSort(&$arr) {
    $len = count($arr);
    // 构建最大堆
    buildHeap($arr, $len);
    
    // 交换并调整
    for ($i = $len - 1; $i > 0; $i--) {
        // 将当前最大值与最后一个元素交换
        swap($arr, 0, $i);
        // 重新调整为最大堆
        heapify($arr, 0, $i);
    }
}

// 构建最大堆
function buildHeap(&$arr, $len) {
    // 从最后一个非叶子节点开始逐个向上调整
    $startIndex = floor($len / 2) - 1;
    for ($i = $startIndex; $i >= 0; $i--) {
        heapify($arr, $i, $len);
    }
}

// 将指定节点及其子节点调整为最大堆
function heapify(&$arr, $index, $len) {
    $largest = $index; // 最大值的索引
    $leftChild = 2 * $index + 1; // 左子节点的索引
    $rightChild = 2 * $index + 2; // 右子节点的索引

    // 找出左、右子节点和当前节点中的最大值
    if ($leftChild < $len && $arr[$leftChild] > $arr[$largest]) {
        $largest = $leftChild;
    }
    if ($rightChild < $len && $arr[$rightChild] > $arr[$largest]) {
        $largest = $rightChild;
    }

    // 若最大值不是当前节点，交换两者的值，并递归地调整交换后的子堆
    if ($largest != $index) {
        swap($arr, $index, $largest);
        heapify($arr, $largest, $len);
    }
}

// 交换数组中两个元素的位置
function swap(&$arr, $i, $j) {
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
}

// 测试代码
$arr = [4, 10, 3, 5, 1];
heapSort($arr);
echo "排序结果：" . implode(", ", $arr);

Le code ci-dessus implémente l'algorithme de tri par tas basé sur un tableau. En appelant la fonction heapSort(), vous pouvez trier un tableau non ordonné et afficher le résultat.

L'algorithme de tri par tas est un algorithme de tri efficace et stable qui peut toujours maintenir des performances élevées lors du traitement de grandes quantités de données. Il est très important que les développeurs comprennent et maîtrisent les principes et les méthodes de mise en œuvre du tri par tas. J'espère que le contenu ci-dessus pourra vous aider à comprendre l'algorithme de tri par tas en 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!