8.2.2 折半插入排序
原书定位
印刷页P340起,对应PDF第352页。下文为目视整理的知识提要;完整内容见原书对照。
用折半查找确定当前元素在已有序前缀中的插入位置,再统一后移记录。为了稳定,应将新元素插在已有相等关键字之后。
比较次数降为 ,但移动次数仍依赖初始次序,平均与最坏总时间仍为 ;辅助空间 。需要数组随机访问,不适合直接套在普通链表上。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P340起,对应PDF第352页。下文为目视整理的知识提要;完整内容见原书对照。
用折半查找确定当前元素在已有序前缀中的插入位置,再统一后移记录。为了稳定,应将新元素插在已有相等关键字之后。
比较次数降为 ,但移动次数仍依赖初始次序,平均与最坏总时间仍为 ;辅助空间 。需要数组随机访问,不适合直接套在普通链表上。

