PHP implementiert einen Patience-Sort-Algorithmus

Patience Sort ist ein Sortieralgorithmus, der vom Kartenspiel Geduld inspiriert und nach diesem benannt ist. Eine Variante dieses Algorithmus berechnet effizient die Länge der am längsten wachsenden Teilsequenz in einem bestimmten Array.

Der Name dieses Algorithmus stammt von einer vereinfachten Version des Geduldskartenspiels. Das Spiel beginnt mit einem gemischten Kartenspiel. Die Karten werden nach den folgenden Regeln nacheinander auf dem Tisch gestapelt.

Zunächst gibt es keinen „Haufen“. Die erste ausgeteilte Karte bildet eine neue Karte, die aus einzelnen Karten besteht.

Jede weitere Karte wird ganz links vom bestehenden „Stapel“ platziert, wobei die oberste Karte einen Wert hat, der größer oder gleich dem Wert der neuen Karte ist, oder rechts von allen bestehenden „Stapel“. “, wodurch ein neuer „Haufen“ entsteht.

Das Spiel ist beendet, wenn keine Karten mehr ausgeteilt werden können.

Dieser Artikel wandelt dieses Kartenspiel in einen zweistufigen Sortieralgorithmus um, wie unten gezeigt. Stellen Sie sich bei einem Array von n Elementen aus einem perfekt geordneten Bereich das Array als eine Sammlung von Karten vor und simulieren Sie das Gedulds-Sortierspiel. Wenn das Spiel endet, wird die sortierte Reihenfolge durch wiederholtes Entfernen der kleinsten sichtbaren Karte wiederhergestellt, d. h. durch eine P-Wege-Zusammenführung von P-Heaps, die jeweils intern sortiert sind.

Das Codebeispiel für PHP, das den Patientensortierungsalgorithmus implementiert, lautet wie folgt:

<?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);

Ausgabe:

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

In diesem Artikel geht es um den Geduldssortierungsalgorithmus Die Einführung ist einfach und leicht verständlich. Ich hoffe, dass sie Freunden in Not hilfreich sein wird.

Das obige ist der detaillierte Inhalt vonPHP implementiert einen Patience-Sort-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!