完成08(16 25|2s449 012345 i=4时的排序过程 j=3 2525449 08 012345 ten j=2 212525 49 08 012345 temp
16 49 16 16 21 25 49 16 25* 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 08 i = 4 时的排序过程 0 1 2 3 4 5 temp 21 25 25* 49 完成 16 08 16 i = 4 j = 3 i = 4 j = 2
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
直接插入排序的算法 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
直接插入排序的算法 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]; } }
算法分析 若设待排序的对象个数为 Llength==n,则该算 法的主程序执行n-1趟。 关键字比较次数和对象移动次数与对象关键字 的初始排列有关。 最好情况下,排序前对象已经按关键字大小从 小到大有序,每趟只需与前面的有序对象序列 的最后一个对象的关键字比较1次,移动2次 对象,总的关键字比较次数为n-1,对泉移动 次数为2(n-1) 直接插入排序是一种稳定的排序方法。 直接插入排序算法的时间复杂度为O(m2)
算法分析 若设待排序的对象个数为L.length= n，则该算 法的主程序执行n-1趟。 关键字比较次数和对象移动次数与对象关键字 的初始排列有关。 最好情况下，排序前对象已经按关键字大小从 小到大有序，每趟只需与前面的有序对象序列 的最后一个对象的关键字比较 1 次，移动 2 次 对象，总的关键字比较次数为 n-1，对象移动 次数为 2(n-1)。 直接插入排序是一种稳定的排序方法。 直接插入排序算法的时间复杂度为O(n2 )
折半插入排序( Binary Insertsort) 折半插入排序基本思想是:设在顺序表中有 个对象序列0,11…,vn-11。其中,v0l 11,…,-1是已经排好序的对象。在插入 v引时,利用折半搜索法寻找v的插入位置
折半插入排序 (Binary Insertsort) 折半插入排序基本思想是：设在顺序表中有一 个对象序列 V[0], V[1], …, v[n-1]。其中，v[0], V[1], …, v[i-1] 是已经排好序的对象。在插入 v[i] 时，利用折半搜索法寻找 v[i] 的插入位置