如何優雅地給撲克牌排序？（一）——排序算法的數學本質

• 2019 年 10 月 8 日
• 筆記

不知平常各位打牌時候是否遇到過這樣的場景：四人打完升級後，面對兩幅混亂的撲克牌，走了一人後想打鬥地主，現在要把他們分出一副來，於是打算先排序後分離，然後各種花色，數字，擺滿一桌子，亂成一團，等排好了，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. 微調順序；