1回答

liuyubobobo

2017-07-23

已采纳

首先一个主要区别在实现上。自顶向下的归并排序使用了递归的方式，而自底向上的归并排序只是迭代。所以自顶向下的归并排序过程使用了系统的栈空间。从这个角度，其实自底向上的归并排序性能更优。在这个课程的官方github中有对这两种方式性能的比较代码，虽然其实对现代计算机来讲，基本可以忽略递归带来的性能开销。

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

另一方面，自顶向下和自底向上，在归并的过程中，划分的数组是不一样的。自顶向下每次都平分数组；但是自底向上永远是以2的幂次的大小不断归并数组。

比如，对于有10个元素的数组，自顶向下的归并过程，先划分成5，5；对于5个元素的数组，划分为2，3；对于3个元素的数组，换分为1，2；对于2个元素，划分为1，1

但是，对于自底向上的归并排序，先划分为10个1，之后合并为5个2，之后合并为4，4，2，之后合并为8，2，最后合成10个元素有序的状态，可以看出，这个划分过程，是和自顶向下的归并过程不一样的。

5

1

charlenellll

谢谢老师！

2018-01-05

共1条回复