什么是patience sort算法？相信很多人對(duì)patience sort算法的了解處于一知半解狀態(tài)，小編給大家總結(jié)了以下內(nèi)容。如下資料是關(guān)于patience sort算法的內(nèi)容。

成都創(chuàng)新互聯(lián)公司主營(yíng)嶗山網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,成都APP應(yīng)用開(kāi)發(fā),嶗山h5微信平臺(tái)小程序開(kāi)發(fā)搭建,嶗山網(wǎng)站營(yíng)銷(xiāo)推廣歡迎嶗山等地區(qū)企業(yè)咨詢

耐心排序（patience sort）是一種排序算法，靈感來(lái)源于紙牌游戲patience，并以此命名。該算法的一個(gè)變體可以有效地計(jì)算給定數(shù)組中最長(zhǎng)遞增子序列的長(zhǎng)度。

該算法的名字來(lái)源于一個(gè)簡(jiǎn)化版的patience紙牌游戲。這個(gè)游戲以一副洗牌開(kāi)始。按照下面的規(guī)則，這些卡片被一個(gè)接一個(gè)地摞在桌子上。

最初，沒(méi)有"堆"。發(fā)出的第一張牌形成一張由單張牌組成的新牌。

隨后的每一張牌被放置在現(xiàn)有"堆"的最左邊，其頂牌的值大于或等于新牌的值，或位于所有現(xiàn)有"堆"的右邊，從而形成新"堆"。

當(dāng)沒(méi)有剩余的牌要發(fā)時(shí)，游戲就結(jié)束了。

本文將此紙牌游戲轉(zhuǎn)化為一種兩階段排序算法，如下所示。給定一個(gè)由n個(gè)元素組成的數(shù)組，這些元素來(lái)自一個(gè)完全有序的域，將這個(gè)數(shù)組看作是紙牌的集合，并模擬patience排序游戲。當(dāng)游戲結(jié)束時(shí)，通過(guò)反復(fù)取出最小可見(jiàn)卡，恢復(fù)排序后的序列;換句話說(shuō)，執(zhí)行p堆的p-way合并，每個(gè)p堆都是內(nèi)部排序的。

PHP實(shí)現(xiàn)耐心排序算法的代碼實(shí)例如下：

<?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) {
        //二進(jìn)位檢索
        $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);
    }
    // 優(yōu)先隊(duì)列允許我們有效地合并堆
    $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實(shí)現(xiàn)patience sort算法的具體操作，代碼詳細(xì)清楚，如果在日常工作遇到這個(gè)問(wèn)題，希望你能通過(guò)這篇文章解決問(wèn)題。如果想了解更多相關(guān)內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

名稱(chēng)欄目：PHP實(shí)現(xiàn)patiencesort算法-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://www.aaarwkj.com/article46/hoieg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供用戶體驗(yàn)、微信小程序、做網(wǎng)站、響應(yīng)式網(wǎng)站、網(wǎng)站維護(hù)、網(wǎng)站營(yíng)銷(xiāo)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)