13.10 归并排序

优质

小牛编辑

126浏览

2023-12-01

在第13.7节，我们见到一个简单的排序算法，结果它不够高效。要排序n个项目，该算法必须遍历向量n次，而且每次遍历花的时间也是与n成比例的。因此，总时间与n2（这里表示n平方，下同）成比例。

本节我们会简单介绍一个更高效的算法——归并排序。要对n个项目进行排序，归并排序消耗的时间与nlogn成比例。这个数字看起来可能不会给人留下深刻印象，但是随着n增大之后，n2和nlogn的差距是巨大的。你可以自己找一些n值来试试看。

归并排序背后的基本思路是：如果有两个子牌堆，每个都是已经排序好的，那将它们合并成一个有序的牌堆是很容易的（而且很快速）：

形成两个子牌堆，每个牌堆大约10张纸牌，分别排序，正面朝上时最小的牌在最上面。让这两个牌堆都正面朝你。
比较每个牌堆最上面的纸牌，选择小的并将它翻过来放到归并后的牌堆中。
重复步骤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成为递归的，所有你需要做的就是用这个排序函数替换掉老的。没有理由读不同的程序。

实际上你必须考虑正确的基本条件，还要确认最终能到达基本条件，但除此之外，写一个递归版本应该是没什么问题的。祝你好运！