PHP implémente un algorithme de tri par patience

Patience sort est un algorithme de tri inspiré du jeu de cartes patience et qui porte son nom. Une variante de cet algorithme calcule efficacement la longueur de la sous-séquence croissante la plus longue dans un tableau donné.

Le nom de cet algorithme vient d'une version simplifiée du jeu de cartes de patience. Le jeu commence par un jeu de cartes mélangé. Les cartes sont empilées les unes après les autres sur la table selon les règles suivantes.

Au départ, il n'y a pas de "tas". La première carte distribuée forme une nouvelle carte composée de cartes individuelles.

Chaque carte suivante est placée à l'extrême gauche de la "pile" existante, la carte du dessus ayant une valeur supérieure ou égale à la valeur de la nouvelle carte, ou à droite de toutes les "piles" existantes. ", formant ainsi un nouveau "tas".

Le jeu est terminé lorsqu'il n'y a plus de cartes à distribuer.

Cet article transforme ce jeu de cartes en un algorithme de tri en deux étapes comme indiqué ci-dessous. Étant donné un tableau de n éléments d'un domaine parfaitement ordonné, considérez le tableau comme une collection de cartes et simulez le jeu de tri par patience. Lorsque le jeu se termine, la séquence triée est restaurée en supprimant à plusieurs reprises la plus petite carte visible ; en d'autres termes, en effectuant une fusion p-way de p-tas, dont chacun est trié en interne.

L'exemple de code PHP implémentant l'algorithme de tri des patients est le suivant :

<?php
class PilesHeap extends SplMinHeap {
    public function compare($pile1, $pile2) {
        return parent::compare($pile1->top(), $pile2->top());
    }
}
function patience_sort($n) {
    $piles = array();
    //排序成堆
    foreach ($n as $x) {
        //二进位检索
        $low = 0; $high = count($piles)-1;
        while ($low <= $high) {
            $mid = (int)(($low + $high) / 2);
            if ($piles[$mid]->top() >= $x)
                $high = $mid - 1;
            else
                $low = $mid + 1;
        }
        $i = $low;
        if ($i == count($piles))
            $piles[] = new SplStack();
        $piles[$i]->push($x);
    }
    // 优先队列允许我们有效地合并堆
    $heap = new PilesHeap();
    foreach ($piles as $pile)
        $heap->insert($pile);
    for ($c = 0; $c < count($n); $c++) {
        $smallPile = $heap->extract();
        $n[$c] = $smallPile->pop();
        if (!$smallPile->isEmpty())
            $heap->insert($smallPile);
    }
    assert($heap->isEmpty());
}
$a = array(100, 54, 7, 2, 5, 4, 1);
patience_sort($a);
print_r($a);

Sortie :

Array 
( 
[0] => 100 
[1] => 54 
[2] => 7 
[3] => 2 
[4] => 5 
[5] => 4 
[6] => 1 
)

Cet article concerne tri des patients (Cette introduction à l'algorithme de tri par patience est simple et facile à comprendre. J'espère qu'elle sera utile aux amis qui en ont besoin !

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!