知识卡片

普通读书笔记卡 · 5654.c.3.b.1.a

归并先解决两侧再线性合并

理解等级:中级

归并排序先把区间分成两半,递归排好后,用两个游标从两个有序子区间的头部选较小者,放入临时数组,再复制回原区间。先子问题后合并,与后序处理结构一致。

每层合计线性、层数对数,时间nlogn;数组实现峰值辅助空间线性,不能只计对数递归栈。左右相等时先取左项,才能让跨两半同键保持输入先后。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      观察发现,归并排序与二叉树后序遍历的递归顺序是一致的。 ‧ 后序遍历 :先递归左子树,再递归右子树,最后处理根节点。 ‧ 归并排序 :先递归左子数组,再递归右子数组,最后处理合并。 归并排序的实现如以下代码所示。请注意,

    参考来源

    - 位置:《Hello 算法--Go版本》第11章《排序》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[28924,29034)) - 结论依据:实际merge/mergeSort与<=取左、临时数组完整代码支持。 - 原始内容:观察发现,归并排序与二叉树后序遍历的递归顺序是一致的。 ‧ 后序遍历 :先递归左子树,再递归右子树,最后处理根节点。 ‧ 归并排序 :先递归左子数组,再递归右子数组,最后处理合并。 归并排序的实现如以下代码所示。请注意,