知识卡片

结构图卡 · 6067.x

归并排序分解与合并

理解等级:中级

归并排序递归地把序列拆成两部分,子序列有序后再逐层合并。若每次近似对半,递推式为T(N)=2T(N/2)+O(N):每层合并工作总量约N,共约log₂N层,因此时间为O(N log N)。图中38、27、43等数只是教学输入,未实际执行排序。

结构图:

flowchart TD
 A[拆分原序列] --> B[左半递归排序]
 A --> C[右半递归排序]
 B --> D[合并两个有序序列]
 C --> D
 D --> E[得到当前序列的有序结果]
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      合并这两个子问题,需要的代价是O (N )。 归并排序的求解过程如图9-1所示。 图9-1 归并排序的求解过程

    参考来源

    - 位置:《代码精进之路:从码农到工匠(异步图书)》9.1.1 归并排序(spine2;extracted/代码精进之路:从码农到工匠(异步图书)/_epub-src/OEBPS/text00001.html;u144-ch09-006)。 - 结论依据:原文在“合并这两个子问题,需要的代价”附近的定义、实例或代码支撑本卡的核心说明:归并排序递归地把序列拆成两部分,子序列有序后再逐层合并。适用边界按该处前提解释,代码未执行。 - 原始内容:合并这两个子问题,需要的代价是O (N )。 归并排序的求解过程如图9-1所示。 图9-1 归并排序的求解过程