PHP は忍耐ソート アルゴリズムを実装します

ペイシェンス ソートは、カード ゲームの忍耐力からインスピレーションを受け、それにちなんで名付けられた並べ替えアルゴリズムです。このアルゴリズムの変形では、指定された配列内の最も長く増加するサブシーケンスの長さを効率的に計算します。

このアルゴリズムの名前は、忍耐カード ゲームの簡易版に由来しています。ゲームはシャッフルされたトランプのデッキから始まります。カードは次のルールに従ってテーブル上に次々と積み重ねられます。

当初は「ヒープ」はありませんでした。最初に配られたカードは、個々のカードで構成される新しいカードを形成します。

後続の各カードは、既存の「山」の左端に配置され、一番上のカードの値が新しいカードの値以上であるか、既存のすべてのカードの右に配置されます。積み重ねて、新しい「ヒープ」を形成します。

配られるカードがなくなるとゲームは終了します。

この記事では、このカード ゲームを以下に示す 2 段階のソート アルゴリズムに変換します。完全に順序付けされたドメインからの n 個の要素の配列が与えられた場合、その配列をカードのコレクションとして考え、忍耐の並べ替えゲームをシミュレートします。ゲームが終了すると、表示されている最小のカードを繰り返し削除することによって、ソートされたシーケンスが復元されます。つまり、それぞれが内部でソートされた p ヒープの p 方向マージを実行します。

患者並べ替えアルゴリズムを実装する PHP のコード例は次のとおりです:

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

出力:

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

この記事は忍耐並べ替えアルゴリズムについてです。シンプルで分かりやすい紹介ですので、困っている友達のお役に立てれば幸いです！

以上がPHP は忍耐ソート アルゴリズムを実装しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。