Code d'implémentation du tri par tas PHP

Le tas peut être considéré comme un arbre binaire complet. À l'exception de la couche la plus basse, chaque niveau est plein, ce qui permet au tas d'être représenté par un tableau, et chaque nœud correspond à un élément du tableau.
La relation entre les tableaux et les tas :
Les tas binaires sont généralement divisés en deux types : le tas maximum et le tas minimum.
Tas maximum : la valeur de l'élément de chaque nœud parent dans le tas est supérieure ou égale à son nœud enfant (s'il existe)

Tas minimum : la valeur de l'élément de chaque nœud parent dans le tas ; est inférieur ou égal à son nœud enfant (s'il existe)

Qu'est-ce que le tri par tas

Le tri par tas (en supposant que le tas maximum soit utilisé) consiste à retirer le nombre maximum au niveau du nœud enfant ; en haut du tas, et continuez à ajuster le tas restant au tas maximum

Algorithme de tri du tas

Construire un tas : Construire un tas est un processus d'ajustement constant du tas, en commençant par len /2 et aller au premier nœud, où len est le nombre d'éléments dans le numéro de tas. Le processus de construction d'un tas est un processus linéaire. Le processus d'ajustement du tas est toujours appelé de len/2 à 0, ce qui équivaut à o(h1) + o(h2) ... + o(hlen/2) où h représente la profondeur du nœud, len /2 représente le nombre de nœuds. Il s'agit d'un processus de sommation et le résultat est linéaire O(n).

Tas d'ajustement : le tas d'ajustement sera utilisé dans le processus de construction du tas, et sera également utilisé dans le processus de tri du tas. L'idée d'utiliser est de comparer le nœud i et ses nœuds enfants gauche(i), droit(i), et de sélectionner le plus grand (ou le plus petit) des trois si le plus grand (petit)

Sortie :

<?php
// PHP 堆排序算法实现、堆排序时间复杂度分析
/**
 * 堆排序
 * @param array $arr
 */
function heap_sort(array &$arr)
{
    $count = count($arr);
    // 建堆 (下标小于或等于floor($count/2)-1的节点都是要调整的节点)
    for($i = floor($count / 2) - 1; $i >= 0; $i --)
    {
        heap_adjust($arr, $i, $count);
    }
    // 调整堆
    for($i = $count - 1; $i >= 0; $i--)
    {
        //将堆顶元素与最后一个元素交换
        swap($arr,0,$i);
        heap_adjust($arr,0,$i - 1);
    }
}
/**
 * 交换2个值
 * @param array $arr
 * @param int $a 数组下标
 * @param int $b 数组下标
 */
function swap(array &$arr, $a, $b)
{
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}
/**
 * 交换2个值
 * @param array $arr
 * @param int $start 数组下标
 * @param int $end 数组下标
 */
function heap_adjust(array &$arr, $start, $end)
{
    $temp = $arr[$start];
    //沿关键字较大的孩子节点向下筛选，这里数组开始下标识0
    for($j = 2 * $start + 1; $j <= $end; $j = 2 * $j + 1)
    {
        if($j != $end && $arr[$j] < $arr[$j + 1])
        {
            $j ++;
        }
        if($temp < $arr[$j])
        {
	        //将根节点设置为子节点的较大值
	        $arr[$start] = $arr[$j];
	        $start = $j;
        }
    }
    $arr[$start] = $temp;
}
// 使用
$arr = array(8,4,2,9,3,7,1,6,5);
heap_sort($arr);
print_r($arr);

Le tri par tas est une méthode de tri instable (l'ordre des mêmes éléments avant et après le tri peut changer).

Recommandations associées :

Explication détaillée du tri des tas en JavaScript

Explication détaillée du tri des tas de l'algorithme de tri PHP

Explication détaillée de l'exemple d'algorithme de tri de tas 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!