在第13.7節，我們見到一個簡單的排序算法，結果它不夠高效。要排序n個項目，該算法必須遍歷向量n次，而且每次遍歷花的時間也是與n成比例的。因此，總時間與**n2**（這里表示n平方，下同）成比例。 本節我們會簡單介紹一個更高效的算法——歸并排序。要對n個項目進行排序，歸并排序消耗的時間與nlogn成比例。這個數字看起來可能不會給人留下深刻印象，但是隨著n增大之后，n2和nlogn的差距是巨大的。你可以自己找一些n值來試試看。 歸并排序背后的基本思路是：如果有兩個子牌堆，每個都是已經排序好的，那將它們合并成一個有序的牌堆是很容易的（而且很快速）： 1. 形成兩個子牌堆，每個牌堆大約10張紙牌，分別排序，正面朝上時最小的牌在最上面。讓這兩個牌堆都正面朝你。 2. 比較每個牌堆最上面的紙牌，選擇小的并將它翻過來放到歸并后的牌堆中。 3. 重復步驟2直到其中一個牌堆為空時為止。然后將剩下的牌加到歸并后的牌堆中。 我們得到的結果就是一個有序的牌堆。該算法的偽代碼看起來是這個樣子的： ~~~ Deck merge (const Deck& d1, const Deck& d2) { // 創建一個足夠保存所有牌的新牌堆 Deck result (d1.cards.length() + d2.cards.length()); // 使用索引i記錄在當前處理的第一個牌堆中的位置 // 使用索引j記錄第二個牌堆中的位置 int i = 0; int j = 0; // 索引k用于遍歷保存結果的牌堆 for (int k = 0; k<result.cards.length(); k++) { // 如果d1為空，選擇d2；如果d2為空，則選擇d1 // 否則，比較兩張紙牌 // 將選擇的紙牌加入到結果牌堆中 } return result; } ~~~ 因為兩個參數是對稱的，所以我選擇將merge設計為非成員函數。要測試merge函數，最好的方法莫過于創建一副牌并洗牌，使用subdeck函數將牌分為兩小堆，然后使用上一章的sort函數將兩個子牌堆排序。之后，你就可以把這兩個子牌堆傳給merge函數來驗證下它能否正常工作了。 如果你能讓這一想法稱為可行的，請嘗試一下mergeSort的一個簡單實現： ~~~ Deck Deck::mergeSort () const { // 找到牌堆的中點 // 將牌堆劃分為兩個子牌堆 // 使用sort函數對子牌堆進行排序 // 合并兩個子牌堆并返回結果 } ~~~ 注意，當前對象聲明為const，因為mergeSort不需要修改它。 相反，函數中創建了一個新的Deck對象并返回。 如果你能讓這一版本正常工作，真正有趣的事情要開始了！mergesort的神奇之處在于，它是遞歸的。在對子牌堆進行排序時，為什么要調用老版本的較慢的sort函數？為什么不調用我們正在編寫的這個出色的、新的mergeSort函數？ 這不僅是一個好想法，為了取得我承諾的性能優勢，這也是必要的。盡管為了讓它能正常工作，你必須添加一個基本條件，這樣才不會無限遞歸下去。一個簡單的基本條件是，子牌堆中有沒有牌或者只有1張牌。如果mergesort接受的是這樣小的子牌堆，不需要修改就可以直接返回，因為這樣的牌堆已經是有序的。 遞歸版本的mergesort看起來應該是這個樣子的： ~~~ Deck Deck::mergeSort (Deck deck) const { // 如果牌堆中只有0或1張紙牌，直接返回該牌堆 // 找到牌堆中的中點 // 將牌堆劃分為兩個子牌堆 // 使用mergeSort對子牌堆進行排序 // 將兩個子牌堆合并到一起并返回該結果 } ~~~ 像往常一樣，思考遞歸程序有兩種方法：一個是考慮清楚完整的執行流程，另一個就是通過“思路跳躍”的方式。我有意的通過構造這個例子鼓勵你使用“思路跳躍”來思考問題。 當使用sort來對子牌堆進行排序的時候，你并沒有感覺到不得不跟蹤執行流程，對不對？ 這正是因為你假設了sort函數能正常工作，因為你已經調試過這個函數。好了，要讓mergeSort成為遞歸的，所有你需要做的就是用這個排序函數替換掉老的。沒有理由讀不同的程序。 實際上你必須考慮正確的基本條件，還要確認最終能到達基本條件，但除此之外，寫一個遞歸版本應該是沒什么問題的。祝你好運！