8.2.1 直接插入排序

教材导航 · 第8章

原书定位

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

保存当前元素,从有序前缀尾部向前比较,把大于它的记录依次后移,再填入空位。只移动严格较大者可保持相等关键字的相对顺序,因此稳定。

顺序数组实现辅助空间 O(1)O(1);最好已序时 O(n)O(n),平均与最坏 O(n2)O(n^2)。忽略哨兵比较时,逆序最坏记录比较 n(n−1)/2n(n-1)/2 次,正序为 n−1n-1 次。

适合规模较小或基本有序的数据。链表可通过修改链接实现插入,定位插入点仍需遍历。

直接插入排序过程

直接插入排序过程,原书P340。

对应练习

8.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P339,PDF第351页

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