如何优雅地给扑克牌排序？（一）——排序算法的数学本质

不知平常各位打牌时候是否遇到过这样的场景：四人打完升级后，面对两幅混乱的扑克牌，走了一人后想打斗地主，现在要把他们分出一副来，于是打算先排序后分离，然后各种花色，数字，摆满一桌子，乱成一团，等排好了，5分钟过去了……

图1 乱七八糟的扑克牌

或者你是课代表老师让你把全班同学的作业按照学号排序，结果你又把作业本排满了一桌子也没排好，惨不忍睹……

图2 乱七八糟的作业本

当然有时候在接头表演魔术的时候，连桌子都没有，只能用双手完成排序，发现更困难了……

本篇探讨的问题就是从这些事情中抽象出来的一个魔术常用的场景：对于一副完全洗乱的扑克牌（去大小王），在不借助桌面等外物放置的条件下，怎样才能最快地按照A-K和黑红梅方的花色的顺序完成整副牌的排序？

图3 完整扑克牌排序

这个问题很有意思，且听我一一道来。

计算机科学中的排序算法

注意哈，这里是计算机科学，不是工程，更不是魔术，我们用科学研究的方法，抛去细枝末节，来先研究一下问题的核心。

排序是计算机科学中对集合内元素（注意是元素，只是他们经常用数组存放而已）进行相邻有序排列的一个基本和经典的算法，其思路之广，变种之多，让人感叹计算机科学的魅力，可谓是人类计算机历史上值得一提的宝贵财富。

然而算法只不过是离散数学结论的表达，而程序更是算法的执行而已，作为排序这个数学问题本身，有很多重要的点，比如其时间空间复杂度分析，上限的确定，是有明确的理论界定的。又比如，一些容易忽视的点：

排序结果的本质是什么？待排序的元素之间要满足什么条件？

而我们无论是生活中，还是一些科学计算的应用场景，排序必不可少，光背下那些算法的流程是不够的，我们还应当从数学的角度理解之，方可应用之，拓展之。我们下面的分析中会逐步回答上面提出的问题和思考。

我对排序本质的数学理解：

对于有限集合A中的任何两个对象a, b，存在一个布尔值为值域的函数f（一般地，1表示大于，0表示小于）定义了在A上的一个二元关系集（A ^ 2的子集）： Comp = {(a, b) | f(a, b) = 1}，如果满足传递性，即若(a, b), (b, c)属于Comp，则(a, c)属于Comp；且(a, b)和(b, a)有且只有一个属于Comp，那么这样的集合总数为|A|!个，该函数的值可由一个A所有元素的有序排列上个元素的位置关系前后来确定。而排序就是去求得这一满足该关系的序列的过程。

或者从另一个角度看，该关系构成一个全部元素的DAG（有向无环图），且边的数量有n (n - 1) / 2，其中唯一能遍历所有元素的迹（trail）上的顶点序列即为所求的排序序列。

以上关系反过来说可能更简洁：排序是求一个能遍历所有待排序元素的迹构成的有向图，表示其在集合中的大小关系以及相邻情况，由此任何两个元素的大小关系等价为能以哪个元素为起点通过迹达到哪个元素的问题。这便是排序的本质。

此时甚至不需要知道元素用来排序的数值属性，根据这个图就可以直接推断谁在谁前面，谁是第一和倒数第一等问题了。

比如数值的大小关系（又比如集合之间的包含关系等）就是一种满足如上条件的关系和集合（如果有严格相等的数，可以重合为同一个元素（集合元素的特异性）或者把大于等于和小于看成是划分方式，以免漏掉元素），其直观感觉就是他们在一个序轴上有固定的位置，其大小运算是其位置关系的演算而已；又比如球队之间的胜负关系并不满足这样的性质，火箭胜马刺，马刺胜骑士，骑士却还可以赢火箭。所以，排序的前提是其“有序”关系的存在，或理解为关系的传递性，或理解为序轴上的位置的相对比较。这是对待排序集合的元素的要求。

图4 有序关系的唯一排序序列

好了，这样看来，搞清楚了排序问题的基本数学结构，我们就有两种基本思路来获取这个待排序的集合的元素上的有序关系到底是哪一个序列了：

（这里注重原理分析和讲解，具体有10来种排序算法的代码，复杂度分析结论算法导论或者网上很容易搜到，这里不赘述了。）

1. 比较类排序

通过一定的策略来查找比较函数f(a, b)的值，以此在最少的空间和时间内获取最终排序；

这类排排序方法的时间复杂度可以从信息论角度证明出一个理论的下界：

原始集合A的熵H(A) = log(|A|!)，每一次比较能带来的最大信息量为H(Comp)max = log 2, 这个的前提是每次比较都恰好有一半可能大和小；所以完成熵为0的最终唯一有序序列需要的比较次数最少为（运用Stirling公式，m = |A|）:

（这是该策略下此问题的理论边界，任何试图超越的尝试都是徒劳的，我们应当在这个边界内找到稳定的方法就去调整其他策略了，这里的边界思维在吴军老师的谷歌方法论中也多次提到，我们有机会也会再专门讲讲数学与魔术的边界，欢迎继续关注。）

可见，基于比较的排序算法不可能拿到比O(mlogm)更低的空间复杂度，而归并，快排，堆排序就达到了这个界，我们理解了他们的做法就好，不需要在徒劳了，另外，他们依次将空间复杂度降低到了O(m), O(logm), O(1)，而快排最坏时间复杂度为O(m ^ 2)，就稳定性而言，只有归并排序是稳定（是否保证相等的对象排序不变）的。这些策略的共同特点是，一定没有一次比较是徒劳的，即每一次都通过比较结果获得了1bit的信息。不像那些冒泡，选择，插入排序等，他们中有很多比较是无用的，即通过有序关系性质看起来是不需要的多余步骤，因此才在时间复杂度上吃了亏达到O(m ^ 2)。

2. 非比较类排序

把各个元素放到相应的原始有序数轴上去，再依次取值即可。

典型的有计数排序和基数排序，当然还有直接的桶排序，他们都可以做到接近O(m)的时间复杂度，能够这么做的前提是预知所有元素的已知整数轴上的取值范围，并以此为空间复杂度来安放他们，显然只有依次安放+取出这两个O(m)的操作而已，复杂度的理想情况当然是O(m)啦，但是，实际使用中不免有冲突，或者有多位数可以降低空间复杂度的诱惑下选择了基数排序（或者一些字符串字典序的比较天然就符合这一场景），我们需要根据机器条件和对速度的要求，稳定性等，灵活来选用它们。

当然，再细化来看，我们可以根据输入数据的一些细微特性去调整算法，结合以上比较和放置类排序的思想，以期达到空间，时间最好，平均，或最坏的结果，哪怕不是复杂度的降低，工程上也是有意义的。Python中的sort函数就利用了这些微妙的性质。因为对于实际输入序列，总有诸如分布特性稳定，部分有序等等，我们可以进行一些预估来大大减少排序时间，比如，快排中随机找一个数可能导致最坏情况下两侧极不均匀，所以，如果能够用一小部分数据估计分布的中位数等各个分位数，直接用数值来区分，会得到更稳定的结果；又比如，若对变量服从的分布都稳定估计的话，可以用预估策略接近O(loglogn)的时间复杂度，当然估计越准确越接近了。

另外，教科书上教的是排序算法，但实际中也要看到我们具体问题来灵活运用其思想，那些经典的面试题诸如求最大的k个数，求中位数等，如果只是把答案背下来没有理解的话，是搞不定的，但是如果理解了排序的数学本质和算法运用原理（递归，分治等），现场推导出来也不是什么难事。就像我们学数学规划从来没必要去背单纯形法的公式一样，把这些排序算法背下来也不见得能够用好他们。而关键是要掌握背后的排序原理和复杂度分析方法，才能分析实际问题中原始数据分布特征以及运算资源条件，以解决一切和集合的序有关甚至超出的问题，这些知识才真正为我们所用。

顺便说一下，以上分析是自E.Knuth（高德纳）先生发明计算机科学评价算法优劣的方案：时间和空间复杂度以来所形成的算法的科学分析范式，它考察的是当处理问题的规模为无穷时候，运算时间/空间的增长趋势，而并不关系常数倍数，或者其他时间细节，因为确实，在两个算法比较优劣的时候，在规模无穷大的时候，起作用的就仅有这个增涨趋势本身了。这种思维方式极具科学价值，使得我们的研究可以落在核心问题上而大胆地忽略细枝末节。

但是，在做工程实际问题的时候，却是另一种思路，倍数，哪怕是常数层次的改进也很关键，甚至实际中也没有哪个变量是无穷大的，所以，各个因素也要综合考量，包括机器资源限制，运行环境条件，使得效率最高地获取工程可用的代码。

好了，现在可以回到我们一开始的问题：在实际生活中我们也经常遇到给作业本，扑克牌等排序的场景，那么在这种人工操作的条件下，怎样的策略才是最优的呢？

这其实是一件很有趣的事情，想想你拿起扑克牌排序的时候，终于可以手持那看不见摸不着的内存上存着的数组上的元素了，可以自己执行自己写的算法玩了！

可直接拿着扑克牌执行计算机上最优的排序算法不见得是一件很容易的事情，因为碳基的大脑和硅基的计算机所擅长的操作还真的不一样，不信你去执行一下归并或者快排中的递归试试，保证执行到三四层就差不多摆满一桌子牌而且记不清递归顺序了，而这些在堆栈的数据结构下计算机可以轻易地实现这种递归，自顶向下的方式几千几万层也毫不费力，而人脑并不擅长记忆这些层次。

因此，我们得想想，如何把科学的扑克牌排序算法应用到实际扑克牌排序中，这应该算是一次科学到工程的实践吧，去考虑一些科学划定边界以后却不曾考虑清楚的实际情况，对同学们的工程思维的养成应该也大有裨益吧。

这里给出John Hamman发表在他的大作《The Secrets of Brother John Hamman》中发表的一个排序方案，大家可以从视频中窥探一二，我初学之，顿觉大师思路之美妙，看看你是否能从中体会一二，想想，这种方案具体是用了怎样的排序算法？为什么这种算法被人所采用？还有没有继续改进的空间呢？

视频1 John Hamman Sorting Cards

这里也给出视频中5轮操作的具体过程，其中前四轮都是Cull牌到底部，最后是微调：

1. Cull 1, 2, 3, 7, 8, 9到底部；

2. Cull 4, 5, 6, 1, 2, 3到底部；

3. Cull红色的牌到底部；

4. Cull梅花和红心到底部；

5. 微调顺序；