8.2.2 折半插入排序

教材导航 · 第8章

原书定位

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

用折半查找确定当前元素在已有序前缀中的插入位置,再统一后移记录。为了稳定,应将新元素插在已有相等关键字之后。

比较次数降为 O(nlog⁡n)O(n\log n),但移动次数仍依赖初始次序,平均与最坏总时间仍为 O(n2)O(n^2);辅助空间 O(1)O(1)。需要数组随机访问,不适合直接套在普通链表上。

对应练习

8.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P340,PDF第352页

原书对照,原书P341,PDF第353页