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

来源：藏色散人 发布时间：2019-03-13 10:38:53 阅读量：854

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

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

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

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

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

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

PHP实现耐心排序算法的代码实例如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

<?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);

输出：

1

2

3

4

5

6

7

8

9

10

Array

(

[0] => 100

[1] => 54

[2] => 7

[3] => 2

[4] => 5

[5] => 4

[6] => 1

)


标签： PHP 环境搭建
分享：
评论：
你还没有登录，请先

热门标签

热门文章

    推荐文章