【勘误】自底向上的归并排序在实现上的小修正

来源: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

1
0

算法与数据结构(C++版) 面试/评级的算法复习技能包

课程专为:短时间内应对面试、升职测评等艰巨任务打造

11218 学习 · 1617 问题

查看课程