【勘误】自底向上的归并排序在实现上的小修正
来源:3-4 自底向上的归并排序算法

liuyubobobo
2017-01-08
在这一小节,我们介绍了自底向上的归并排序。其中,sz是merge这个归并过程中待归并的两个数组的大小,因此,我们在遍历这个sz的时候,是不需要它等于n的。因为sz = n的时候,一定没有第二个子数组和这个sz = n的子数组进行归并的。所以,我们的循环中,sz < n 就足够了。
具体的,MergeSortBU的非优化版本如下:
for( int sz = 1; sz < n ; sz += sz ) for( int i = 0 ; i < n ; i += sz+sz ) __merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1) );
代码在本课程的官方github上已经更新:https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/04-Merge-Sort-Bottom-Up/main.cpp
写回答
1回答
-
苏丛JS
2019-08-09
第二个for的条件应该是 i + sz < n
10
相似问题