知识卡片

普通读书笔记卡 · 1897.d

归并排序将局部有序合成整体

理解等级:中级

递归把数组分成更小子数组,单个元素可以直接视为有序,再将两个有序子序列逐层合并,得到全体有序结果。这里合并必须保留全部元素及重复次数,只拼接两个有序序列并不能保证整体有序。它说明分解后的局部成果需要符合原问题要求的整合操作。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      分治算法主要包含3个步骤:分、治、并。 “分”是递归地将原问题分解成小问题;“治”是在解决了各个小问题之后(各个击破之后)合并小问题的解,从而得到整个问题的解;“并”是按原问题的要求,将子问题的解逐层合并,构成原问题的解。 以归并排序为例,该算法在1945年由冯·诺伊曼

    参考来源

    - 位置:《程序员的底层思维》第7章《分治思维》(来源项目book-sources,`extracted/程序员的底层思维/_epub-src/Cheng Xu Yuan De Di Ceng Si Wei_split_011.html`)。 - 结论依据:原文从“分治算法主要包含3个步骤:分、治、并。 “分”是递归地将原问题分”展开,与本卡的“递归把数组分成更小子数组,单个元素可以直接视为有序,再将两个有序子序列逐层合并,得到全体有序结果”对应;正文额外解释的限制、反例或外部校正均不冒充原书保证。 - 原始内容:分治算法主要包含3个步骤:分、治、并。 “分”是递归地将原问题分解成小问题;“治”是在解决了各个小问题之后(各个击破之后)合并小问题的解,从而得到整个问题的解;“并”是按原问题的要求,将子问题的解逐层合并,构成原问题的解。 以归并排序为例,该算法在1945年由冯·诺伊曼