知识卡片
归并排序分解与合并
归并排序递归地把序列拆成两部分,子序列有序后再逐层合并。若每次近似对半,递推式为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 归并排序的求解过程