如何优雅地给扑克牌排序？（二）——排序算法的一次工程实践

在上一篇文章中，我们一起探讨了排序类问题的数学本质，其问题的真实适用范围以及由此定义下能够证明有效的两类排序算法流程，分析了他们的适用范围和时间，空间上的复杂度边界，让我们对这类问题有了全面的认识。

那今天我们要探讨的，如何给一副完全洗乱的扑克牌仅用双手排序的问题（不允许借助桌面等类似内存作用的地方），可以看作是学好了科学，划定了边界以后的一次工程实践。

如果以上算是一次小型的科学研究思考，那么转化为技术，还需要一些工程的实践，我们以“把计算机科学的排序算法迁移到人给扑克牌排序”这个问题为例来说明，看你能不能体会出科学和工程的区别，以及分别的妙处。

这个问题很有意思，首先，科学上最好的快排和归并其实都不怎么好，你想想每次都要突出来一张牌标明左右分别大于或者小于它，或者归并的序列估计要摆满一桌子，这有多麻烦。而这些操作在计算机上不过是递归罢了，不过是不断地把数据压入栈顶再一股脑倒出来，对应的是CFG（上下文无关文法）的解析器，即LBA（线性有界自动机）。而且实际运行过程的每一步对计算机来说都及其高效而不会出错。

看到了吧，我们面临的问题非常棘手，我们的双手单位操作时间远远长于计算机，而且递归几十层人类也会疯掉，直接套用在计算机科学理想条件下最优的方式来让人执行并发挥不出优势，况且我们也就需要处理52张牌而已。

于是拿起扑克牌端详了起来，有这么几点想法：

1. 人的双手要想迅速完成批量操作，摆一桌子是不现实的，需要找到人能批量完成的操作；

2. 其实，完整的一副扑克牌是范围给定且连续无间断的，这样看起来比一般任意集合排序容易，因为明确知道2后面是3，而不用担心中间还需要插入什么，即每个元素都有有精确的桶，或者叫槽位；

3. 扑克牌的点数有两位数表达，低位是13进制的，高位是4进制的，这个天然可以用基数排序，再利用桶获得接近线性的复杂度；

4. 对于3~5张牌，尤其是还相邻的牌，人类不需要什么章法也能迅速的排序，换句话说，如果我们能够先粗排，再精排，像快排那样分块，或者阶梯分班那样培养，或是搜索排序那样先效率高地简单算一把以后再精排，是一个不错的办法；

5. 判断一张牌是否是某点数范围，是否是某花色比要比较任意两张牌要快，比较同花色/同数字的两张牌大小也比任意比较要快很多；

好了，这一切都有前辈们思考过了，魔术师们凭借着对自己双手和大脑的直觉，设计出了一些方案来做出这些酷炫的效果，上期我们已经提到，这期我们先回顾一下：这个方法是John Hamman发表在他的大作《The Secrets of Brother John Hamman》中的，并一直流传着，请看视频：

视频1 John Hamman Sorting Cards

可以看到，整个过程一共进行了4词Cull操作和一次微调，其具体流程为：

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

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

3. Cull红色的牌到底部；

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

5. 微调顺序；

在这个流程里，我上面提到的几点想法在这个作品中也完全体现出来了：

1. Cull是一个隐秘而又可以快速批量进行的魔术手法，还考验魔术师的手法功底，而一次Cull等价于一次二分桶的hash！

2. 用到的就是基数排序，对于13进制的A-K的低位，我们用两次二分桶完成了1-3, 4-6, 7-9, 10-K的该位上的粗排，神奇的是，这个粗排性质在高位排序后不会受到影响！这恰是基数排序 背后的数学原理保证的！随后，对4进制的花色位再次进行了二次而分桶，这样花色位的排序就完全完成了；

3. 最后仅剩下3-4张同花色，仅数字不同，还连号，知道具体范围的位置微调，遍历一遍即可完成；

经过噼里啪啦一顿操作，方才混乱的扑克牌居然恢复了顺序！简直是奇迹！

再一次体现了，魔术师真的是带着镣铐跳舞，用最简单的手法操作，用计算机的思维，组合出绝妙的效果。

还没完，无论是数学家，还是魔术师，亦或是我们数学魔术师，最赖以生存的品质就是精益求精，钻研到底。到目前为止，我们学习了John Hamman在处理“扑克牌人工快速排序”时候留下的经验，并且经过思考剖析，理解了这么设计的原理，包括计算机复杂度分析的方法以及在特定条件下如何用工程思维调整地策略。这些分析也许发明者自己都没意识到，也许是他太聪明，意识流里想出来的方法，但是我们学习者，一定要探究其原理，才能为己所用，不然就只是傻乎乎追星了。

好了，到了学习成长最关键的一步了，既然已经站在了巨人的肩膀，并且站稳了，不妨再向上跳一步：John Hamman的方法设计从原理上讲还有没有改进的空间，哪些部分还不是最优的？

显然，这个方案的弊病其实也很明显，那就是4次的Cull操作其实非常刺眼，实地考察实验会发现，这个方法虽然像个谦谦君子般优雅，但是比一些直觉化的，没有什么章法铺满一地的方案快不了多少，真是乱拳打死老师傅啊。老师傅一定要在智慧上碾压后辈，才能被年轻人尊敬啊。

为什么需要4次Cull呢，那是因为两个进制位，等效四进制的每位需要两次二桶hash才能够完成，能不能够把桶数直接改到4个，使得这个hash过程一次性完成呢，这样就只需要两次操作了，答案是可以的！请看视频！

视频2 Quaternary sorting Cards Method

Cull的手法天然是一个二分桶，利用的是扑克序列可以依据两个竖直方向起点位而分开，而这个方向到3都很困难，因为会找不到插入口。但是，横向方向还没有使用啊，如果把这两个组合起来，恰好完成了两个二分桶达到四进制位的完全排序效果，所需的基本排序次数直接减半！

有了这个想法以后，最开始发现要hold住4个序列的Cull有点困难，其实有一点手法基础和牌感，一点不难的，关键是，它的效果很让人激动人心啊，直接把4次Cull缩减为2次，几乎达到时间减半的效果，这简直是算法和人手的天作之合！邓爷爷说的对啊，科学技术是第一生产力啊！科学给予指导，技术在生产环境下实践出效果来，做的是提高量级的事情啊！怎么不让人激动！

而最后的微调方式上也可以有一些微优化，我经过一些测试，感觉对于人类来说，直接观察初始顺序，按照插入排序方案逐个找到值从小到大的牌即可，或者因为这是个已知完全集合，哪些牌是确定的，可以相当于构造无冲突hash，总之熟练以后，可以迅速微调得到最后解。

有同学可能会提问了，你这个方法也不见得多快啊？为什么一开始我们要限定不使用桌面呢？有桌面的话，就我们往常经验，把不同抽出来花色排成四叠，再一叠一叠地摊开按照数字抽取排序，甚至轻而易举可以超过上面所谓设计精妙的方案啊！

其实你没有想错，我们如果借助桌面，开扇出来hash出花色和找到点数排序，这相当于是每个时刻，眼睛都可以同时并行搜索到多张同花色以及多张相邻的值的牌，虽然手上功夫是串行的，但是瓶颈一定在眼睛的查找速度上，因为手的速度几乎就是发一遍扑克牌的速度。所以当我们可以在计算机上有并行资源的时候，总是可以在数量级上实现效率的飞跃。如果扑克牌排序也这样做，那也是极好的。

比如，对于快排和归并排序，其在可否并行时的递归表达式为：

所以，就比较排序而言，有并行资源时候，还能再把速度提高一个log数量级，但是，完全并行是理想的，还需要考虑到计算机或者人的资源量等实际因素，在扑克牌排序问题上，显然是有显著提高的，并行而灵活地查找以及排序是人乃以生存的远超机器的能力，但是可以想见，如果扑克牌的张数更多到几百几千张，这些小把戏都都在海量的条件下失效了。要清楚地明白，计算机复杂度是在变量趋于无穷时候的性质，但是实际工程问题并不会无穷，故要灵活对待和处理。

从计算机基于比较和非比较的排序算法，到特定环境下的一次排序实战，我们体会了计算机科学的美，给我们划定了一条边界和方法论的指导；另外，在实际环境中在给定条件和要求范围内解决问题也是我们看重的能力，是作为一个工程师的必备素养。相信你在凭借兴趣开心地学习的过程中，能够领悟这些道理，迅速地成长。