void Insertsort(sqlist &lt for(i=2; i<=Llength; ++ 数据结构 if(L. ri]. key<L r[i-1. key)& Lr10=L.r{i;∥复制哨兵∥ for(j=i-1; L. rlo. key<L. rIj. key;--j) L rlj+l=Lrlj; L rlj+1=L rlo I 部 序}/O(n*n) 性能分析:(1)时间复杂度:O(n*n) (2)空间复杂度:O(1 (3)排序方法是稳定的 算法分析 >空间上,只需i,j两个整型变量和一个记录的 数据结构 辅助空间r0l,r0作为“监视哨”,控制待插入 元素相对于有序子文件为最小时WHIE循环 的结束,同时也用于暂存待插入元素。 时间上,只包含比较关键字和移动记录两种 操作 当待排序初始文件按关键字非递减有序(正序)时: 内部排序 >对每个记录只进行一次比较,整个排序过程共 进行了∑1=n-1次比较(最少); 每个记录都要进行r移到r0和r0移到rj+1两 次移动,因此共移动2(n-1次(最少)6 数 据 结 构 之 内 部 排 序 11 void InsertSort(SqList &L){ for(i=2; i<=L.length;++i) if(L. r[i]. key<L.r[i-1]. key){ L.r[0]=L. r[i]; //复制哨兵// for(j=i-1;L. r[0]. key<L. r[j]. key;--j) L. r[j+1]=L. r[ j ]; L. r[j+1]=L. r[ 0 ]; } } //O( n*n ) 性能分析：（1）时间复杂度：O(n*n) （2） 空间复杂度：O(1) （3）排序方法是稳定的 数 据 结 构 之 内 部 排 序 12 ¾ 算法分析 ¾空间上，只需i，j两个整型变量和一个记录的 辅助空间r[0], r[0]作为“监视哨”，控制待插入 元素相对于有序子文件为最小时WHILE循环 的结束，同时也用于暂存待插入元素。 ¾时间上，只包含比较关键字和移动记录两种 操作。 ¾当待排序初始文件按关键字非递减有序(正序)时： ¾ 对每个记录只进行一次比较，整个排序过程共 n 进行了∑1=n-1次比较(最少)； i=2 ¾ 每个记录都要进行r[i]移到r[0]和r[0]移到r[j+1]两 次移动，因此共移动2(n-1)次(最少)