PHP实现耐心排序（patiencesort）算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了PHP实现耐心排序（patiencesort）算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1851字，纯文字阅读大概需要3分钟。

内容图文

耐心排序（patience sort）是一种排序算法，灵感来源于纸牌游戏patience，并以此命名。该算法的一个变体可以有效地计算给定数组中最长递增子序列的长度。

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

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

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

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

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

本篇文章就是关于耐心排序（patience sort）算法的介绍，简单易懂，希望对需要的朋友有所帮助！

以上就是PHP实现耐心排序（patience sort）算法的详细内容，更多请关注Gxl网其它相关文章！

内容总结

以上是互联网集市为您收集整理的PHP实现耐心排序（patiencesort）算法全部内容，希望文章能够帮你解决PHP实现耐心排序（patiencesort）算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---