在前几篇文章的评论中，有时会有一些指责-如果世界上已经有最快的快速排序，为什么还要研究其他任何排序。 他们说，所有这些奇特的异国情调都没有用，也没有人需要。


珀西·迪亚科尼斯 （ Percy Diaconis ）一直研究纸牌排序，认为这是手动排列一副纸牌的最快方法。

因此，如果没有一位受人尊敬的数学家（和一位经验丰富的纸牌魔术师）说谎，那么根据该算法的实际价值，一切都会井井有条。

现在注意你的手。

阶段1.叠放

因此，从甲板上取走蠕虫。 它们将代表13个随机元素的数组。



我们需要将卡片分解成几堆，以使卡片在每个堆中都是有序的序列。

换句话说，我们现阶段的任务是从现有的未排序数组中快速创建几个有序子数组。 同时，非常希望这些子阵列的数量更少，这意味着您需要努力确保这些子阵列更真实。 这样做如下。

第一张牌是第一堆的开始。



我们依次将卡片转移到该堆叠中，直到下一张转移的卡片小于堆叠中最上面的卡片为止。

而且，每个堆栈都是一个堆栈-我们不使用整个堆栈，而只能使用放在最后的最上面的卡。



如果当前卡大于堆栈中的最小卡，则必须创建一个新的卡堆，当前卡会打开一个新的堆栈。



堆栈的顺序很重要！ 如果他们的数量已经超过一个，则我们将下一张牌不是放在最后一堆中，而是放在最左边的一堆中，我们可以将它放在其中。

现在，那位女士之后，我需要在某个地方附加一个9。 从机械上讲，我想将卡片放在第二堆中，但是在第一堆中，最上面的卡片是九个以上。 因此，我们可以继续第一个堆栈而不会违反其顺序。 顺便说一句，接下来的三个，紧跟着九个，进入第一堆。



不能将七个和六个添加到第一堆中（它们大于其中的顶部卡片），但是它们在第二个堆中仍具有位置。



王牌开始了新的一堆。 剩余的琐事将落入不同的托盘中，具体取决于可将其插入的堆栈向左多远。



结果，卡片被分成几堆。 在每堆中，纸牌是降序排列，顶部是最小的纸牌。 桩是堆。

因为我们首先尝试填充左侧的堆栈，所以我们形成了最小的数量。 如果我们只是在数组中四处走动并从中提取出递减的子数组，那么堆自然会变得更大。

第二阶段。最底行

向下移动可用的顶部卡，使它们排成一排。 如果堆栈是堆栈，那么我们将像队列一样处理最下面一行。



重要的是，堆中可用的顶牌也是有序的。 最下面一行已按升序排序。 这并不奇怪-形成纸牌叠时，较小的纸牌被发送到左侧。

将来，直到分类结束，我们对桌上摆放的所有卡牌都不感兴趣。 只需要这些：

• 队列最底端的最左边的卡片（我们称之为当前卡片）。
• 在堆栈堆栈中，我们仅与可用的顶级卡一起使用。 在这种情况下，仅需要直接位于当前地图上和左侧的那些桩。 此时不需要右边的桩。

在底行中，我们从卡片的左到右对卡片进行排序。 最左边是当前的最小值，我们将其返回到原始的第一行。 同时，每次我们将另一张卡返还给基地时，有必要将另一张卡放回原处。 从哪里得到的？ 在当前地图上方和左侧（在可用卡中）的堆中，选择一个最小值，该最小值将移动到底部行中当前左侧卡的空位置，然后从此处移至主阵列。

数组中的两个立即返回。 空出的位置由三元组占据（我们将其从第一堆移至最下面的行），并且从最下面的行开始，该三元组作为当前的最小值到达主数组。 在前两堆中，再次搜索最小值（这是四堆），这也会返回。 五成为当前的最小值，依此类推。



很快地将工作与队列的升序和堆栈的降序结合起来，我们得到了从最小到最大的所有元素。 总的来说就是这样。

此过程的动画。



如果将以上所有内容翻译成Python，则会得到以下结果：

from functools import total_ordering from bisect import bisect_left from heapq import merge @total_ordering class Pile(list): def __lt__(self, other): return self[-1] < other[-1] def __eq__(self, other): return self[-1] == other[-1] def patience_sort(n): piles = [] # sort into piles for x in n: new_pile = Pile([x]) i = bisect_left(piles, new_pile) if i != len(piles): piles[i].append(x) else: piles.append(new_pile) # use a heap-based merge to merge piles efficiently n[:] = merge(*[reversed(pile) for pile in piles]) 

参考文献

耐心排序 （ Google-translate ）

耐心排序源

普林斯顿CS：增长最快的子序列

耐心分类桩的组合 （ Google-translate ）

Wiki摘要：患者分类

字对齐 （ Google翻译 ）

系列文章：

• Excel应用程序AlgoLab.xlsm
• 交换排序
• 插入排序
  • 图书管理员排序
  • 纸牌排序
  • 排序“河内塔”
  • 年轻表排序
  • 反转排序
  • 插入排序比较
• 按选择排序
• 合并排序
• 按分布排序
• 混合排序

在AlgoLab应用程序中，此排序现在处于活动状态。 同时，可视化有两种模式：卡形式（默认模式）和数字形式。 但是，对于纸牌样式，必须使数组中的最大元素和最小元素之差小于54（甲板上的纸牌数量，包括两个小丑）。 如果不满足此条件，或者完全关闭了卡模式（为此，您需要在带有排序名称的单元格的注释中写入card = 0），那么可视化将采用钝数字形式。

西服按优先级排列： 峰<俱乐部<手鼓<心。


就是说，手鼓的任何卡片比俱乐部套的任何卡片大，心服的任何卡片比高峰套的任何卡片大，等等。 如果我们用数字进行类比，则峰值从0到9，棍棒从10到19，菱形从20到29，心从30到39（是的，当然，在西服套装中，卡的数量不完全是10，但是您了解什么意思）。 至于诉讼中的资历，这很普通：从平局到王牌。 您还可以选择比所有其他牌都老的小丑。 在这种情况下，红色小丑比黑色更重。

本文是在EDISON Software（一家专业的Web开发公司，最近重新设计其网站）的支持下撰写的。