如何優雅地給撲克牌排序？（二）——排序演算法的一次工程實踐

• 2019 年 10 月 8 日
• 筆記

在上一篇文章中，我們一起探討了排序類問題的數學本質，其問題的真實適用範圍以及由此定義下能夠證明有效的兩類排序演算法流程，分析了他們的適用範圍和時間，空間上的複雜度邊界，讓我們對這類問題有了全面的認識。

那今天我們要探討的，如何給一副完全洗亂的撲克牌僅用雙手排序的問題（不允許藉助桌面等類似記憶體作用的地方），可以看作是學好了科學，劃定了邊界以後的一次工程實踐。

如果以上算是一次小型的科學研究思考，那麼轉化為技術，還需要一些工程的實踐，我們以「把電腦科學的排序演算法遷移到人給撲克牌排序」這個問題為例來說明，看你能不能體會出科學和工程的區別，以及分別的妙處。

這個問題很有意思，首先，科學上最好的快排和歸併其實都不怎麼好，你想想每次都要突出來一張牌標明左右分別大於或者小於它，或者歸併的序列估計要擺滿一桌子，這有多麻煩。而這些操作在電腦上不過是遞歸罷了，不過是不斷地把數據壓入棧頂再一股腦倒出來，對應的是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數量級，但是，完全並行是理想的，還需要考慮到電腦或者人的資源量等實際因素，在撲克牌排序問題上，顯然是有顯著提高的，並行而靈活地查找以及排序是人乃以生存的遠超機器的能力，但是可以想見，如果撲克牌的張數更多到幾百幾千張，這些小把戲都都在海量的條件下失效了。要清楚地明白，電腦複雜度是在變數趨於無窮時候的性質，但是實際工程問題並不會無窮，故要靈活對待和處理。

從電腦基於比較和非比較的排序演算法，到特定環境下的一次排序實戰，我們體會了電腦科學的美，給我們劃定了一條邊界和方法論的指導；另外，在實際環境中在給定條件和要求範圍內解決問題也是我們看重的能力，是作為一個工程師的必備素養。相信你在憑藉興趣開心地學習的過程中，能夠領悟這些道理，迅速地成長。