C++ 歸并排序

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

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

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

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

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

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

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

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

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

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

如果你能讓這一想法稱為可行的，請(qǐng)嘗試一下mergeSort的一個(gè)簡(jiǎn)單實(shí)現(xiàn)：

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

注意，當(dāng)前對(duì)象聲明為const，因?yàn)閙ergeSort不需要修改它。 相反，函數(shù)中創(chuàng)建了一個(gè)新的Deck對(duì)象并返回。

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

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

遞歸版本的mergesort看起來應(yīng)該是這個(gè)樣子的：

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

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

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

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

實(shí)際上你必須考慮正確的基本條件，還要確認(rèn)最終能到達(dá)基本條件，但除此之外，寫一個(gè)遞歸版本應(yīng)該是沒什么問題的。祝你好運(yùn)！