PHP实现耐心排序（patience sort）算法

该算法的名字来源于一个简化版的patience纸牌游戏。这个游戏以一副洗牌开始。按照下面的规则，这些卡片被一个接一个地摞在桌子上。

最初，没有 堆 。发出的第一张牌形成一张由单张牌组成的新牌。

随后的每一张牌被放置在现有 堆 的最左边，其顶牌的值大于或等于新牌的值，或位于所有现有 堆 的右边，从而形成新 堆 。

当没有剩余的牌要发时，游戏就结束了。

本文将此纸牌游戏转化为一种两阶段排序算法，如下所示。给定一个由n个元素组成的数组，这些元素来自一个完全有序的域，将这个数组看作是纸牌的集合，并模拟patience排序游戏。当游戏结束时，通过反复取出最小可见卡，恢复排序后的序列;换句话说，执行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); // 优先队列允许我们有效地合并堆 $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教程

郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。