void Insertsort(sqlist < 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)次(最少)
当待排序文件按关键字非递增有序逆序) 时 据结构 >记录r[j(=2,3,n)均要和前i-1个记录及r0进 行比较,整个排序过程共进行了 ∑i=(n+2)(n-1)/2次比较(最多); 移动记录次数:每个记录都要进行r订移动到 r0和r移动到r+1两次移动,另外当 内部排序 r[ i-key< rIil. key时,还将r移动到r+1, 所以,当初始文件为逆序时移动记录次数最 多,为 ∑(i-1)+2(n-1)=(n+4)(n-1)2次(最多) 13 数据结构 结论 直接插入排序的效率与待排文件的关 键字排列有关; >直接插入排序的时间复杂度为O(n2); 直接插入排序是稳定的这一点由过程 内部排序 中WHIE语句的条件“<”保证的)。 14
7 数 据 结 构 之 内 部 排 序 13 ¾当待排序文件按关键字非递增有序(逆序) 时 ¾记录r[i](i=2,3,...n)均要和前i-1个记录及r[0]进 行比较，整个排序过程共进行了 n ∑ i=(n+2)(n-1)/2次比较(最多)； i=2 ¾移动记录次数：每个记录都要进行r[i]移动到 r[0]和r[0]移动到r[j+1]两次移动，另外当 r[i].key＜r[j].key时，还将r[j]移动到r[j+1]， 所以，当初始文件为逆序时移动记录次数最 多, 为 n ∑ (i-1)+2(n-1)=(n+4)(n-1)/2次(最多)。 数 据 结 构 之 内 部 排 序 14 ¾结论 ¾直接插入排序的效率与待排文件的关 键字排列有关； ¾直接插入排序的时间复杂度为O(n2)； ¾直接插入排序是稳定的(这一点由过程 中WHILE语句的条件“＜”保证的)
折半插入排序 N Void BInsertSort( Sqlist &l)( 据结构 for(i=2; i<=Llength; ++i)t LroFLr low=l; high=i-1: while( low<=high)t 折半查找位置 m=(low+high)/2; 内部排序 if(Lr[o- key<L rIm. key ) high=m-1; else lowe+l for(j=i-1; j>=high+l;--j)Lr[j+1=Lrl; L rhigh+1FL.r[o: >2-路插入排序 据 例:对初始关键字为{49,38,65,97,76,13,27 49}的序列进行2-路插入排序。 构 解:其2路插入排序的过程如下 初始关键字:4938659776132749 1:(49 内i=2: (38) 排 (4965) 个fnal 个frst
8 数 据 结 构 之 内 部 排 序 15 ¾ 折半插入排序 Void BInsertSort ( Sqlist &L) { for ( i=2; i<=L.length; ++i ) { L.r[0]=L.r[i]; low=1; high=i-1; while ( low<=high) { //折半查找位置 m=(low+high)/2; if ( L.r[0].key<L.r[m].key ) high=m-1; else low=m+1; } for ( j=i-1; j>=high+1; --j) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; } } 数 据 结 构 之 内 部 排 序 16 ¾ 2-路插入排序 例：对初始关键字为{49，38，65，97，76，13，27， 49} 的序列进行2-路插入排序。 解：其2路插入排序的过程如下 初始关键字： 49 38 65 97 76 13 27 49 i=1: (49) first↑ ↑final i=2: (49) (38) ↑final ↑first i=3: (49 65) (38) ↑final ↑first
i=4:(496597) (38) 个fna ↑frst 结i=5:(49657697 个fnal 个frst i=6:(49657697) (1338) 个f 部i=7: 49657697) (132738) 序 个fnal 个frst i-8:(4949657697132738) 个 个frst 与折半插入排序相比,2路插入排序可以减 据 构 少记录移动的次数,但不能避免记录的移动。 此外需要N个额外的存储空间。并且如果Lr 是待排序记录中关键字最小(或最大)的记录 排 时,2路排序就没有优越性可言了。 18
9 数 据 结 构 之 内 部 排 序 17 i=4: (49 65 97) (38) ↑final ↑first i=5: (49 65 76 97) (38) ↑final ↑first i=6: (49 65 76 97) (13 38) ↑final ↑first i=7: (49 65 76 97) (13 27 38) ↑final ↑first i=8: (49 49 65 76 97 13 27 38) ↑final ↑first 数 据 结 构 之 内 部 排 序 18 与折半插入排序相比，2路插入排序可以减 少记录移动的次数，但不能避免记录的移动。 此外需要N个额外的存储空间。并且如果L.r[1] 是待排序记录中关键字最小（或最大）的记录 时，2路排序就没有优越性可言了
表插入排序 如果希望在排序过程中不移动记录,只有改变存储结构,进行表插 据结构 入排序。表插入排序的存储结构用C语言表述如下: #define SIZe 100 静态连表容量 typedef struct RetYpe re /记录项 next 指针项 内部排序 sYNOde 表结点类型 typedef struct( SLNode rSIZE: /0号单元为表头结点 19 nt length 链表当前长度 SLinkList Type /静态链表类型 其实现方法 数据结构 首先将静态链表中数组下标为“1”的分量(结点)和表 头结点构成一个循环链表(表头接点记录的关键字取最 大的整数 MAXINT),然后依次将下标为“2”至“n”的 分量(结点)按记录关键字非递减有序插入到循环链表 中 例:采用表插入排序将下面的序列49,38,65 97,76,13,27,49按从小到大的顺序排列
10 数 据 结 构 之 内 部 排 序 19 ¾ 表插入排序 如果希望在排序过程中不移动记录，只有改变存储结构，进行表插 入排序。表插入排序的存储结构用C语言表述如下： #define SIZE 100 //静态连表容量 typedef struct{ RcdType rc; //记录项 int next; //指针项 }SLNode; //表结点类型 typedef struct{ SLNode r[SIZE]; //0号单元为表头结点 int length; //链表当前长度 }SLinkListType; //静态链表类型 数 据 结 构 之 内 部 排 序 20 其实现方法： 首先将静态链表中数组下标为“1”的分量（结点）和表 头结点构成一个循环链表（表头接点记录的关键字取最 大的整数MAXINT），然后依次将下标为“2”至“n”的 分量（结点）按记录关键字非递减有序插入到循环链表 中。 例：采用表插入排序将下面的序列{49，38，65， 97，76，13，27，49}按从小到大的顺序排列