8.5.1 归并排序

教材导航 · 第8章

原书定位

印刷页P370起,对应PDF第382页。下文为目视整理的知识提要;完整内容见原书对照。

二路归并把两个有序段合为一个有序段,每次取两段首部较小者,某段用完后追加另一段。相等时先取左段记录可保持稳定。

自底向上每趟有序段长度约翻倍,共 ⌈log⁡2n⌉\lceil\log_2 n\rceil 趟;也可递归分半后归并。总时间 O(nlog⁡n)O(n\log n),常规数组辅助空间 O(n)O(n),递归另有 O(log⁡n)O(\log n) 栈。链表归并可重接指针,空间分析需按具体实现。

合并长度 a,b>0a,b>0 的有序数组,直接双指针最多比较 a+b−1a+b-1 次、最少 min⁡(a,b)\min(a,b) 次;记录复制总量仍为 a+ba+b。比较次数的具体值随交错情况变化。

二路归并排序各趟结果

二路归并排序各趟结果,原书P370。

对应练习

8.5 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P370,PDF第382页

原书对照,原书P371,PDF第383页