49 08 16 2 =三 j=0 2525449 08 012345 temp i=4 j=-1 21 2525449 08 0 2345 temp
25 25* 16 16 21 25 49 25* 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 49 25* 08 0 1 2 3 4 5 temp 21 25 25* 49 16 08 16 16 25 21 i = 4 j = 1 i = 4 j = 0 i = 4 j = -1 16
直接插入排序的算法(p265算法101) void InsertSort(sqlist &l) for (int 1=2; K<=Llength; ++1) if (ltL r[i]. key, L ri-1 key)) Lr[ojLr[i;∥Lr为监视哨 for (int jF=1-1; LT(L r[O]. key, L rLi]. key);--j L r[j+1=L r] L r[+l=.rIO
直接插入排序的算法 （p265算法10.1） void InsertSort(SqList &L) { for (int i=2;i<=L.length;++i) if (LT(L.r[i].key,L.r[i-1].key)) { L.r[0]=L.r[i]; // L.r[0]为监视哨 for (int j=i-1; LT(L.r[0].key,L.r[j].key); --j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; } }
算法分析 若设待排序的对象个数为L. length=n,则该算 法的主程序执行n-1趟。 关键字比较次数和对象移动次数与对象关键字 的初始排列有关。 最好情况下,排序前对象已经按关键字大小从 小到大有序,每趟只需与前面的有序对象序列 的最后一个对象的关键字比较1次,移动2次 对象,总的关键字比较次数为n-1,对象移动 次数为2(n-1)
算法分析 若设待排序的对象个数为L.length= n，则该算 法的主程序执行n-1趟。 关键字比较次数和对象移动次数与对象关键字 的初始排列有关。 最好情况下，排序前对象已经按关键字大小从 小到大有序，每趟只需与前面的有序对象序列 的最后一个对象的关键字比较 1 次，移动 2 次 对象，总的关键字比较次数为 n-1，对象移动 次数为 2(n-1)
分析 个记录的辅助存储空间监视哨 比较次数 最小比较次数:Cmn=n-1 最大比较次数:Cm=∑i=n(n-1)/2 平均比较次数:Cnvg=(n1)n+4)4 移动次数 最小移动次数:Mmin=0 最大移动次数:Mm=∑(+1)=(n+4)n-1)/2 平均移动次数:Mg=(n+8)(n-1)/4
分析： ▪ 一个记录的辅助存储空间 监视哨 ▪ 比较次数 ▪ 最小比较次数：Cmin=n-1 ▪ 最大比较次数：Cmax = ▪ 平均比较次数：Cavg=(n-1)(n+4)/4 ▪ 移动次数 ▪ 最小移动次数：Mmin=0 ▪ 最大移动次数：Mmax = ▪ 平均移动次数：Mavg=(n+8)(n-1)/4 − = = − 1 1 1 2 n i i n(n )/ = + = + − n i i n n 2 ( 1) ( 4)( 1)/ 2
若待排序对象序列中出现各种可能排列的概 冬相同,则可取上述最好情况和最坏情况的 平均情况。在平均情况下的关键字比较次数 和对象移动次数约为n2/4。因此,直接插入 排序的时间复杂度为0(n2) 直接插入排序是一种稳定的排序方法
若待排序对象序列中出现各种可能排列的概 率相同，则可取上述最好情况和最坏情况的 平均情况。在平均情况下的关键字比较次数 和对象移动次数约为 n 2 /4。因此，直接插入 排序的时间复杂度为 o(n 2 )。 直接插入排序是一种稳定的排序方法