C++ 歸并排序

在第13.7節(jié)，我們見到一個簡單的排序算法，結(jié)果它不夠高效。要排序n個項目，該算法必須遍歷向量n次，而且每次遍歷花的時間也是與n成比例的。因此，總時間與n2（這里表示n平方，下同）成比例。

本節(jié)我們會簡單介紹一個更高效的算法——歸并排序。要對n個項目進行排序，歸并排序消耗的時間與nlogn成比例。這個數(shù)字看起來可能不會給人留下深刻印象，但是隨著n增大之后，n2和nlogn的差距是巨大的。你可以自己找一些n值來試試看。

歸并排序背后的基本思路是：如果有兩個子牌堆，每個都是已經(jīng)排序好的，那將它們合并成一個有序的牌堆是很容易的（而且很快速）：

1. 形成兩個子牌堆，每個牌堆大約10張紙牌，分別排序，正面朝上時最小的牌在最上面。讓這兩個牌堆都正面朝你。
2. 比較每個牌堆最上面的紙牌，選擇小的并將它翻過來放到歸并后的牌堆中。
3. 重復步驟2直到其中一個牌堆為空時為止。然后將剩下的牌加到歸并后的牌堆中。

我們得到的結(jié)果就是一個有序的牌堆。該算法的偽代碼看起來是這個樣子的：

Deck merge (const Deck& d1, const Deck& d2) {
  // 創(chuàng)建一個足夠保存所有牌的新牌堆
  Deck result (d1.cards.length() + d2.cards.length());

  // 使用索引i記錄在當前處理的第一個牌堆中的位置
  // 使用索引j記錄第二個牌堆中的位置
  int i = 0;
  int j = 0;

  // 索引k用于遍歷保存結(jié)果的牌堆
  for (int k = 0; k<result.cards.length(); k++) {

    // 如果d1為空，選擇d2；如果d2為空，則選擇d1 
    // 否則，比較兩張紙牌
    // 將選擇的紙牌加入到結(jié)果牌堆中
  }
  return result;
}

因為兩個參數(shù)是對稱的，所以我選擇將merge設計為非成員函數(shù)。要測試merge函數(shù)，最好的方法莫過于創(chuàng)建一副牌并洗牌，使用subdeck函數(shù)將牌分為兩小堆，然后使用上一章的sort函數(shù)將兩個子牌堆排序。之后，你就可以把這兩個子牌堆傳給merge函數(shù)來驗證下它能否正常工作了。

如果你能讓這一想法稱為可行的，請嘗試一下mergeSort的一個簡單實現(xiàn)：

Deck Deck::mergeSort () const {
  // 找到牌堆的中點
  // 將牌堆劃分為兩個子牌堆
  // 使用sort函數(shù)對子牌堆進行排序
  // 合并兩個子牌堆并返回結(jié)果
}

注意，當前對象聲明為const，因為mergeSort不需要修改它。 相反，函數(shù)中創(chuàng)建了一個新的Deck對象并返回。

如果你能讓這一版本正常工作，真正有趣的事情要開始了！mergesort的神奇之處在于，它是遞歸的。在對子牌堆進行排序時，為什么要調(diào)用老版本的較慢的sort函數(shù)？為什么不調(diào)用我們正在編寫的這個出色的、新的mergeSort函數(shù)？

這不僅是一個好想法，為了取得我承諾的性能優(yōu)勢，這也是必要的。盡管為了讓它能正常工作，你必須添加一個基本條件，這樣才不會無限遞歸下去。一個簡單的基本條件是，子牌堆中有沒有牌或者只有1張牌。如果mergesort接受的是這樣小的子牌堆，不需要修改就可以直接返回，因為這樣的牌堆已經(jīng)是有序的。

遞歸版本的mergesort看起來應該是這個樣子的：

Deck Deck::mergeSort (Deck deck) const {
  // 如果牌堆中只有0或1張紙牌，直接返回該牌堆

  // 找到牌堆中的中點
  // 將牌堆劃分為兩個子牌堆
  // 使用mergeSort對子牌堆進行排序
  // 將兩個子牌堆合并到一起并返回該結(jié)果
}

像往常一樣，思考遞歸程序有兩種方法：一個是考慮清楚完整的執(zhí)行流程，另一個就是通過“思路跳躍”的方式。我有意的通過構(gòu)造這個例子鼓勵你使用“思路跳躍”來思考問題。

當使用sort來對子牌堆進行排序的時候，你并沒有感覺到不得不跟蹤執(zhí)行流程，對不對？ 這正是因為你假設了sort函數(shù)能正常工作，因為你已經(jīng)調(diào)試過這個函數(shù)。好了，要讓mergeSort成為遞歸的，所有你需要做的就是用這個排序函數(shù)替換掉老的。沒有理由讀不同的程序。

實際上你必須考慮正確的基本條件，還要確認最終能到達基本條件，但除此之外，寫一個遞歸版本應該是沒什么問題的。祝你好運！