《算法(第四版)》 习题2.2.12次线性的额外空间

趁着假期在学算法

边学边做题,然后这题总觉得没有达到题目要求的所有的点


2.2.12次线性的额外空间。


用大小M将数组分为N/M块(简单起见,设M是N的约数)。实现一个归并方法,使之所需的额外空间减少到max(M,N/M):**

  1. 可以先将一个块看做一个元素,将块的第一个元素作为块的主键,用选择排序将块排序;
  2. 遍历数组,将第一块和第二块归并,完成后将第二块和第三块归并,等等。

我的理解是,先把数组分块,然后用选择排序先对块内排序,再以块首元素为主键进行块排序,最后归并。

问题就在第二点的归并上,实在不理解将第一块和第二块归并完成后再将第二块和第三块归并是怎么个操作法

去看了英文原版
图片说明

以及参考了这位博主的博客
图片说明

第二点还是不明确orz
想请教一下大家的思路,谢谢

1个回答

weixin_42907817
扭秧歌的一只泱 这个就是我最后提到的参考过的博客了
2 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问