加载中...

13.10 归并排序


在第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成为递归的,所有你需要做的就是用这个排序函数替换掉老的。没有理由读不同的程序。

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


还没有评论.