2回答

liuyubobobo

2017-05-18

已采纳

在我的课程中，在merge中使用 T aux[r-l+1]; 的方式来开辟辅助数组，是遵守变量在哪里使用，就在哪里定义的软件工程的原则。但是在实际上，如果数据量太大，这样做的缺点是占用了大量的系统栈空间。如果在小一些数据量的情况，你的归并排序是没有问题，相信是遭遇了这种情况。

最简单地解决方案，是将T aux[r-l+1];这样的辅助空间的开辟换做是使用new来进行开辟。我在github上的代码将使用new的方式申请空间打上了注释，请参考：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/03-Merge-Sort-Advance/MergeSort.h

另外，对于大数据量的使用归并排序，有一个很重要的优化方案，就是将归并排序过程所需要使用的辅助空间，一次性在递归调用前全部开辟，之后一参数的形式传给递归过程以及merge辅助函数。我的github上对于这一章的补充代码展示了这个方法，如果有兴趣可以参考：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/Optional-01-MergeSort-Create-aux-Array-Out-of-Merge/MergeSort2.h

0

3

liuyubobobo

回复

青山烟雨青衫客

完全正确哦：）

2017-05-20

共3条回复

青山烟雨青衫客

提问者

2017-05-20

嗯，我明白了，谢谢，栈空间系统中是有限制，而用new的方式是开辟了堆空间，就不会有此问题了。

0

0