該算法的名字來(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í)例如下：

 ?phphtml' target='_blank'>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 )

本篇文章就是關(guān)于耐心排序（patience sort）算法的介紹，簡(jiǎn)單易懂，希望對(duì)需要的朋友有所幫助！

以上就是PHP實(shí)現(xiàn)耐心排序（patience sort）算法的詳細(xì)內(nèi)容，PHP教程

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請(qǐng)第一時(shí)間聯(lián)系我們修改或刪除，多謝。