利用二元樹這個數據結構，或者說工具， 我們就能講解一個經典的計算機算法，叫做錦標賽排序算法，然後用這個算法，解決高盛的那道面試題，即如何從 25 個選手中賽出前三名。

 

先說說錦標賽排序法，顧名思義，它是受到體育比賽的啟發想出來的。

 

在單淘汰的錦標賽中，選手們兩兩比賽， 勝者晉級，敗者被淘汰。比如世界乒乓球錦標賽或者大滿貫網球賽就是這麼進行的。這樣一來，就可以把比賽的賽程和結果對應成一個二元樹。在樹中每一個選手是二元樹中的一個葉子結點，每一場比賽就相當於兩個數字在比大小。數字大的選手獲勝進入下一輪，也就是說比大小，大的那個選手， 進入上一層，成為枝幹上的根。

 

所以，進入到某一輪比賽的選手，其實都是某個子樹幹的根結點。最後的冠軍自然就是整個二元樹的根結點。當然，這種賽制的合理性來自下面一個假設：如果張三贏了李四，李四贏了王五，那麼張三一定能贏王五。

 

也就是說：A > B， B > C，那麼必然有A > C。 我們不妨稱這種合理的假設為〝輸贏的傳遞性〞。

 

只要上面這種勝負的傳遞性成立，通過這種比賽的結果得到的冠軍，一定是最好的選手。但是，第二名是否如此，就難說了。因為冠軍一路打下來，被他刷掉的選手可能水平都不差，只是運氣不好，提前遇到他了，在決賽之前被淘汰了。

 

比如說在某次網球比賽中，德約科維奇（人稱小德）半決賽贏了費德勒，決賽贏了納達爾。小德的冠軍，不會有什麼異議，但你說到底是納達爾該得亞軍，還是費德勒更厲害， 還真不好說。費德勒只能怪自己那次抽籤運氣不好。因此，如果真要較真，就需要把被冠軍淘汰下來的人放到一個組裡再相互比賽，才能知道誰是亞軍。當然，如今體育比賽規則已經成型，大家遵守就好，不必那麼麻煩賽出第二名。

 

但是，在工程中如果要對比兩個數字的大小，總不能說哪個數字最後被最大的比下去， 就是第二大的吧。因此，如果採用類似錦標賽的方法排出了一、二、三名來，第一大的數字可以完全按照錦標賽淘汰制的方式來。但是第二大的數字，就需要從所有與最大數字比較過被淘汰的數字中，再次比較選擇才能確定。當第二大的數字確定後，就可以用這種方法找到第三大的數字了。這種算法，由於受到錦標賽的啟發，因此被稱為是“錦標賽排序法”（也稱為樹形選擇排序）。總結一下這種方法，它分為兩步：

 

1. 第一步，把所有的數字放到二元樹的葉子結點，然後按照錦標賽單淘汰的方式，兩兩比較選出最大的。

 

2. 第二步，對於第二大的，從所有被最大的數字淘汰的數字中選擇。比如在某次比賽中， 被小德淘汰的分別是納達爾、費德勒、穆雷等人，那麼這些人再進行單淘汰，選亞軍。對於第三、第四大的數字，可以以此類推。

 

如果用這種方式將所有的數字排序，算法的複雜度，或者說量級是 N 乘以 Log N , 和快速排序差不多。那麼為什麼不直接使用快速排序，而要發明出這樣一種不太容易理解的算法呢，因為在特定的場合下，它更快速。比如說，如果我們只需要選出第一名，這種算法的複雜度只有N，不是N乘以 Log N。如果還需要選出第二名，則額外增加 Log N 次計算就可以了，對第三名也是如此。也就是說，這種方法在從 N 個選手中選出 K 個選手的事情中特別快。

 

有了上述算法，就可以講解高盛和 Google 的面試題了，當然任何算法用於實際的問題，都需要變通一下。我們先講講高盛的問題，它是這樣出的：

 

假定有二十五名短跑選手比賽競爭金銀銅牌，賽場上有五條賽道，因此一次可以有五個人同時比賽。比賽並不計時，只看相應的名次。假如選手的發揮是穩定的，也就是說如果約翰比張三跑得快，張三比凱利跑得快，那麼約翰一定比凱利跑得快。最少需要幾組比賽才能決出前三名。

 

這道題是一位面試高盛的朋友告訴我的， 他沒有答好，拿來考我，我一下就答上來了。他說你真聰明，我說不是聰明，因為我學過計算機的理論，知道這類問題怎麼解決。你是學金融的，要在40分鐘內想出解法，只能靠智力了。這就如同我的槍是狙擊步槍，有瞄準鏡，打中目標不難，你只有三八大蓋，只能靠射擊水平。

 

後來我再把這個問題拿去問一位在高盛的朋友，他馬上就答上來了，他沒有學過計算機，答上來完全靠智力，說明高盛招的人不是浪得虛名的，因此，如果你是天才，恭喜你， 你的智力會讓你做事比別人容易，但如果你不是，就像我不是一樣，也沒有關係，多掌握幾個工具就好了。

 

這個問題，我又問了很多人，他們大部分需要八次才能找出前三名，他們具體的做法如下：

 

1. 第一步，將 25 名選手分為五個組，每組五個人，為了便於說明，我們不妨把這 25 人根據所在的組進行編號，A1 ~ A5 在 A 組，B1 ~ B5 在 B 組 …… 最後 E1 ~ E5 在最後的E組。然後讓每個組分別比賽，排出各組的名次來。不失一般性（數學中的一種常見表達）, 我們假設他們的名次就是他們在小組中的編號，即A組的名次是 A1、 A2、 A3、 A4、A5， B組和其它組的名次也是類似（如下圖）:

 

 

 

2. 第二步，讓各組的第一名，也就是 A1、B1、C1、D1、E1 再比一次，上圖中是第一排紅顏色的，這樣就能決出第一名。不失一般性，我們假設 A1 在這次比賽中獲勝，這樣我們就知道了第一名。由於 A1 是第一名，根據我們前面講的淘汰賽的問題，A2可能也很厲害，只是運氣不好，小組賽遇到了A1，當A1已經獲得冠軍了，他就應該作為亞軍的候選。接下來，就進入第三步。

 

3. 第三步，A2 和另外四個組的第一名競爭亞軍。如果這一次A2贏了，他顯然是亞軍， 就由A3 遞進參加爭奪第三名的比賽。我在下圖中用紅色圈定了這種情況下參加第八次比賽的五位選手。如果A2沒有贏，另四個組的某個第一名贏了，那個贏的人是亞軍，就由那個組下一位選手遞進，決逐第三名。

 

 

 

4. 第四步，如上圖選出的五個人進行第三名的比賽，至此，前三名全部產生。

 

如果你在面試中告訴對方上面這種方法表現可能算是中規中矩，但不算完美。

 

那麼這個問題最好的答案是什麼呢？其實前六次比賽都是必須的，也就是說，最佳答案的前兩步和上述答案中的前兩步是相同的。但是，在上述方案中，有一個信息被忽略了，那就是在第六組比賽（即五個第一名的比賽）結束之後，最後的兩名已經沒有資格決逐前三名了。我們不妨假設那一次比賽從最快到最慢的結果是 A1、B1、C1、D1、E1。在 D1和E1之前已經有三名選手了，他們肯定不是前三名。

 

那麼誰還會是第二名的候選呢？根據錦標賽排序的原則，直接輸給第一名的人，也就是 A 組中的 A2，以及最後附加賽輸給他的 B1, 僅此兩人而已。接下來我們要問，除了A2 和B1，誰還會是第三名的候選呢？和 A1 在某一組比賽的第三名，他們是A3、C1，或者輸給第二名候選人 B1的人那個人，即B2。

 

因此，第二、三名的候選人一共只有五個，即A2、A3、B1、B2 和 C1（下圖中的紅色選手），剛好湊一組。第七次，讓他們五個人再跑一次即可。這樣加上前六次，只需要賽七組，這是最佳的方法。

 

 

 

這種方法為什麼比很多人想到的賽八次的方法更有效一點？原因可以歸結為兩點：

 

1. 首先是少做了一些無用功。

 

在八次的比法中間，最後兩次讓D1、E1不斷參加沒有必要的比賽，實際上是浪費資源。有些人寫的計算機軟體速度快，有些人的慢，主要差別在於那些慢的軟件，多做了很多無用功。

 

2. 其次，要善用信息。

 

前幾次比賽的結果裡面有很多有用的信息，比如其實已經篩選出了前三名的候選，這些信息要善於使用。

 

這道題雖然是高盛出的，我覺得拿來考計算機專業的人更合適一些，可以考察他們所學的專業知識，而且可以考察他們應用計算機知識解決其他問題的應變能力。我問過一位高盛的主管總監 ( MD )，為什麼要出這道題？因為它和金融無關。那位朋友講，高盛在招人時，總要照顧一些關係戶，這雖然不公平，但是也沒有辦法。但是，剩下來的人就必須能一個人幹兩個人的活了，一個前提就是人必須聰明，這種題其實就是考智力。當然，從這個問題的解法上你已經看出，善於掌握工具 ( 錦標賽排序 )，可以彌補智力上的不足。

 

明天，我們沿著今天的思路再往前走一步，用這種方法解決Google的一道面試題。

 

最後邀請你思考一下：從錦標賽排序，你獲得了什麼啟發？

 

 

 

來源：《吳軍-計算機經典算法：錦標賽排序算法》