8.2.1 直接插入排序
原书定位
印刷页P339起,对应PDF第351页。下文为目视整理的知识提要;完整内容见原书对照。
保存当前元素,从有序前缀尾部向前比较,把大于它的记录依次后移,再填入空位。只移动严格较大者可保持相等关键字的相对顺序,因此稳定。
顺序数组实现辅助空间 ;最好已序时 ,平均与最坏 。忽略哨兵比较时,逆序最坏记录比较 次,正序为 次。
适合规模较小或基本有序的数据。链表可通过修改链接实现插入,定位插入点仍需遍历。

直接插入排序过程,原书P340。
对应练习
关联知识
原书对照
展开原书对照截图

