不同的具体实现方法导致不同的算法描迷 直接插入排序(基于顺序查找) 折半插入排序(基于折半查找) 表插入排序(基于链表存储) 希尔排序(基于逐描缩小增量) 14
直接插入排序（基于顺序查找） 表插入排序（基于链表存储） 不同的具体实现方法导致不同的算法描述 折半插入排序（基于折半查找） 希尔排序（基于逐趟缩小增量）
直接插入排序 利用“顺序查找”实现 “在R[-1查找R的插入位置” 算法的实现要点
一、直接插入排序 利用 “顺序查找”实现 “在R[1..i-1]中查找R[i]的插入位置” 算法的实现要点：
°从R[i-起向前进行顺序查找, 监视哨设置在R[0 RIOT Ri j插入位置 R[O]=R[i]; ∥设置“哨兵 for g=i-1; R[OJ. key<RiI. key;--j) ∥从后往前找 循环结束表明R的插入位置为j+1
从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[ikey的记录,并在查找的 同时实现记录向后移动; for (j=i-1; R[O]. key<Ri]. key; --j) RIj+1=rlj RIOT 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 上述循环结束后可以直接进行“插入” 插入位置
令i=2,3 实现整个序列的排序。 for (1-2 1-n;++1) if(r[]. key<Ri-1.key 在R[-1]中查找R的插入位置; 插入R[订];
令 i = 2，3，…, n, 实现整个序列的排序。 for ( i=2; i<=n; ++i ) if (R[i].key<R[i-1].key) { 在 R[1..i-1]中查找R[i]的插入位置; 插入R[i] ; }