趁着假期在学算法
边学边做题,然后这题总觉得没有达到题目要求的所有的点
2.2.12次线性的额外空间。
用大小M将数组分为N/M块(简单起见,设M是N的约数)。实现一个归并方法,使之所需的额外空间减少到max(M,N/M):**
- 可以先将一个块看做一个元素,将块的第一个元素作为块的主键,用选择排序将块排序;
- 遍历数组,将第一块和第二块归并,完成后将第二块和第三块归并,等等。
我的理解是,先把数组分块,然后用选择排序先对块内排序,再以块首元素为主键进行块排序,最后归并。
问题就在第二点的归并上,实在不理解将第一块和第二块归并完成后再将第二块和第三块归并是怎么个操作法
去看了英文原版
以及参考了这位博主的博客
第二点还是不明确orz
想请教一下大家的思路,谢谢