教育部—微软精品课程建设项目 实现“一趟插入排序”可分三步进行 1.在R[-1查找R的插入位置, R[1.小].key≤R[].key<R[+1.-1]key; 2.将R[+1-1中的所有记录均后移 个位置; 3.将R插入(复制到R+的位置上 南京航空航天大学数据结构课题组版权所有
实现“一趟插入排序”可分三步进行： 3．将R[i] 插入(复制)到R[j+1]的位置上。 2．将R[j+1..i-1]中的所有记录均后移 一个位置； 1．在R[1..i-1]中查找R[i]的插入位置， R[1..j].key R[i].key < R[j+1..i-1].key；
教育部—微软精品课程建设项目 不同的具体实现方法导致不同的算法描迷 直接插入排序(基于顺序查找) 折半插入排序(基于折半查找) 表插入排序(基于链表存储 希尔排序(基于逐描缔小增量 南京航空航天大学数据结构课题组版权所有
直接插入排序（基于顺序查找） 表插入排序（基于链表存储） 不同的具体实现方法导致不同的算法描述 折半插入排序（基于折半查找） 希尔排序（基于逐趟缩小增量）
教育部—微软精品课程建设项目 直接插入排序 利用“顺序查找”实现 在R[1i-1中查找R的插入位置 算法的实现要点 南京航空航天大学数据结构课题组版权所有
一、直接插入排序 利用 “顺序查找”实现 “在R[1..i-1]中查找R[i]的插入位置” 算法的实现要点：
教育部—微软精品课程建设项目 o从R[i-起向前进行顺序查找, 监视哨设置在R[0 RIO Ri j插入位置 rIO=Ri ∥设置“哨兵 for g=i-1; R[OJ. key<Rii. key;-j) ∥后往前找 循不结束表明R的插入位置为/+知 南京航空航天大学数据结构题组版权所有
从R[i-1]起向前进行顺序查找， 监视哨设置在R[0]； R[0] = R[i]; // 设置“哨兵” 循环结束表明R[i]的插入位置为 j +1 R[0] j R[i] for (j=i-1; R[0].key<R[j].key; --j); // 从后往前找 插入位置 j=i-1
教育部—微软精品课程建设项目 ◎对于在查找过程中找到的那些关键 字不小于R[i]key的记录,并在查找的 同时实现记录向后移动; for g=1-1; R[O]. key<R[]. key; --j) RIj+1=Riil R[0 R[ 插入位置 °上述循环结束后可以直接进行插入 南京航空航天大学数据结构课题组版权所有
对于在查找过程中找到的那些关键 字不小于R[i].key的记录，并在查找的 同时实现记录向后移动； for (j=i-1; R[0].key<R[j].key; --j); R[j+1] = R[j] R[0] j R[i] j= i-1 上述循环结束后可以直接进行“插入” 插入位置