2回答

liuyubobobo

2016-11-14

已采纳

很好的问题。首先抛结论：自底向上的归并排序，是比自顶向下的归并排序要快的。

但有可能，我在课程中实验的结果，自底向上的归并排序反而显得慢了一些。我在课程中没有对自顶向下和自底向上两个版本的归并排序做系统的比较。借你的好问题，我们在这里认真地比较一下。

首先说明一下，课程中为了节省时间，我的测试算法性能的代码都是运行一次就得出结论的。这种方式我们可以看到一个大概，但是不够准确。因为计算机在某一个时刻可能会有特殊的状态或者任务，从而干扰我们的算法运行。最好的方法，是反复运行一个算法多次，取时间的平均值，作为算法性能的衡量标志。

另外，在课程中，我的自顶向下和自底向上的归并排序，全部都使用插入排序进行了优化。要知道，插入排序的性能和测试用例的有序情况极其相关。所以，如果对于两种排序，我们不使用相同的测试用例，看到的时间差也不能准确反映两种排序算法的快慢。因为不同的测试用例会影响算法的性能。

为此，我特别准备了一套代码。测试两种方式下的算法性能。测试方法是对100万级别的数据进行归并排序，每种排序运行100遍，最后以平均值作为衡量排序算法性能的依据。与此同时，我比较了对两种归并排序进行优化和不优化的结果。我的测试代码可以看这里：https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/Optional-02-MergeSort-and-MergeSortBU-Perfermance-Comparison

我的运行结果如下。你也可以尝试多运行几遍，具体时间会有变化，但是趋势应该不会变化。

Without Any Optimization:
Merge Sort    Average Run Time: 0.413346 s
Merge Sort BU Average Run Time: 0.385853 s

With Optimization:
Merge Sort    Average Run Time: 0.359648 s
Merge Sort BU Average Run Time: 0.355589 s

我们可以看到。两次结果，自底向上的实现都更快一些。但是当我们对两种算法进行优化以后，这个速度差别变得很小。这是为什么呢？我们下面仔细分析一下。

我们对归并排序主要有两个优化。第一，使用插入排序对小数组进行处理。这个优化对两个算法的作用是相同的。

关键在于第二条优化。也就是在真正执行merge操作前，先看一下两个子数组是不是真的需要merge。要注意，在自顶向下的归并排序中。这个优化可以发生在非常高的层次，也就是面对两个很大的数组，也可以通过这步优化，使得我们不需要进一步处理两个大数组！但是在自底向上的归并排序中，我们却不能跨过具有这种性质的大数组，依然要一步一步从小数组向上构造。由于这个原因，自底向上的归并排序的速度被拖慢了！

但如你所说，递归调用需要额外的开销。因此，在我们的优化的例子里，两种方式的性能相差不多。不过在我的计算机上，我尝试了多次，基本上自底向上的归并排序在性能上还是会非常微弱的稍胜一筹。你也可以试试看：）

另外，要提一点。虽然递归调用确实会有额外的开销，但是在现代计算机上，对于最新的C++编译器，对此都会有所优化。所以考虑递归实现还是非递归实现，在大多数情况下不是我们处理问题要考虑的首要因素。你要看到，在不经过优化的情况下，其实自底向上的归并排序并没有快多少。但是如果改变成为选择排序，对于100万的数据量，算法执行速度将是不可容忍的。这是两种算法本质的差别，而不是具体实现的差别。这一点也是我在这个课程中一再强调的。希望能够仔细体会：）

当然了，如果在面试的时候，提出采用非递归调用会更优一步，肯定会加分的。尤其是对于很多问题，其实非递归算法的实现并不复杂。以后有机会，在算法设计方面，会给大家介绍更多例子的：）

35

7

Grant_Lian

老师，自底向上为什么不能跨过大数组呢？只是省了递归divide的过程，往上的时候如果开头的元素已经满足顺序可以跳过去吗？

2020-03-21

共7条回复

AlignAndy

2020-02-11

我看糊涂了 这段回答

bottom up更快是结论

但是   但是在自底向上的归并排序中，我们却不能跨过具有这种性质的大数组，依然要一步一步从小数组向上构造。由于这个原因，自底向上的归并排序的速度被拖慢了！

0

0