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

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

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

當沒有剩余的牌要發(fā)時，游戲就結束了。

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

PHP實現耐心排序算法的代碼實例如下：

 ?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) { //二進位檢索 $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)先隊列允許我們有效地合并堆 $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 )

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

以上就是PHP實現耐心排序（patience sort）算法的詳細內容，PHP教程

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。