[科普中国]-耐心排序

在计算机科学中，耐心排序（Patience Sort）是将数组的元素分类成很多堆再串接回数组的一种排序算法。受到纸牌游戏耐心的启发和命名。算法的变体有效地计算给定阵列中最长的增加子序列的长度。

简介创建一个堆数组

比较当前指向的元素和每个堆的第一个元素，计算出比当前元素小的堆数量

若当前元素比所有堆的第一个元素大，创建新的堆并加入到堆数组中，否则将当前元素加入到第“比当前元素小的堆数量”个堆

分类完后将每个堆反序然后对每个堆再做耐心排序

最后将每个堆串接并存储回原本的数组

耐心分类与称为弗洛伊德游戏的纸牌游戏密切相关。 这个游戏非常类似于之前描绘的游戏：

发出的第一张牌形成一张由单张牌组成的新牌。

每张后续卡片放置在一些现有的堆上，其顶部卡的值不大于新卡的值，或者放在所有现有桩的右侧，从而形成新的堆。

当没有剩余的牌可以交换时，游戏结束。

游戏的目标是尽可能少地完成游戏。 与耐心排序算法的不同之处在于，不需要在允许的最左边的堆上放置新卡。 耐心分类构成了玩这个游戏的贪婪策略。

Aldous和Diaconis建议将9个或更少的桩定义为n = 52的获胜结果，其发生概率约为5%。

用于找到最长增加子序列的算法

首先，执行如上所述的排序算法。 桩的数量是最长子序列的长度。 每当一张牌放在一堆纸上时，将一个后指针放在前一堆的顶牌上（假设它具有比新牌更低的价值）。 最后，按照最后一堆中顶部牌的反向指针来恢复最长长度的递减子序列; 它的反向是对增长最长的子序列算法的回答。

S. Bespamyatnikh和M. Segal描述了算法的有效实现，不会产生额外的渐近成本（因为后向指针存储，创建和遍历需要线性时间和空间）。 他们进一步展示了如何报告来自相同结果数据结构的所有最长的增长子序列。1

历史耐心分类由C. L. Mallows命名，他将其发明归功于A.S.C. 罗斯在20世纪60年代初。根据Aldous和Diaconis，耐心排序首先被认为是计算Hammersley和A.S.C.计算最长的子序列长度的算法。 Ross和独立的Robert W. Floyd作为排序算法。 初步分析由Mallows完成。弗洛伊德的比赛由弗洛伊德与唐纳德克努特通信开发。

实现示例C++11

#include #include #include using namespace std; templatevector& operator