折半插入排序的算法 void BInsertSort(sqlist &l) f int low, high, mid for(int F2; K<=L length; ++1) f Lr[]=Lri low=1; high=i-1 while (low <= high i mid=(low+high)/2 if (lt Lr[].key, L rmid]. key)) high=mid-1 else low-mid+1;) for (int j=1-1; j>=high+1; nL.rj+1-=Lrj Lrhigh+1=Lr[OT 说明:low或者high+1为插入点稳定排序
◼ 折半插入排序的算法 void BInsertSort(SqList &L) { int low,high,mid; for (int i=2;i<=L.length;++i) { L.r[0]=L.r[i]; low = 1; high=i-1; while (low <= high) { mid = (low+high)/2; if (LT(L.r[0].key,L.r[mid].key)) high=mid-1; else low=mid+1; } for (int j=i-1; j>=high+1;--j) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; } } 说明：low 或者 high+1为插入点 稳定排序
算法分析 对分查找比顺序查找快,所以对分插入排序 就平均性能来说比直接插入排序要快 它所需要的关键字比较次数与待排序对象序 列的初始排列无关,仅依赖于对象个数。 当n较大时,总关键字比较次数比直接插入 排序的最坏情况要好得多,但比其最好情况 要差。 对分插入排序是一个稳定的排序方法
算法分析 对分查找比顺序查找快，所以对分插入排序 就平均性能来说比直接插入排序要快。 它所需要的关键字比较次数与待排序对象序 列的初始排列无关，仅依赖于对象个数。 当 n 较大时，总关键字比较次数比直接插入 排序的最坏情况要好得多，但比其最好情况 要差。 对分插入排序是一个稳定的排序方法
希尔排序( Shell sort) 希尔排序方法又称为“缩小增量”排序。 该方法的基本思想是:先将整个待排对象序列 按照一定间隔分割成为若干子序列,分别进行 直接插入排序,然后缩小间隔,对整个对象序 列重复以上的划分子序列和分别排序工作,直 到最后间隔为1,此时整个对象序列已“基本 有序”,进行最后一次直接插入排序
希尔排序 (Shell Sort) 希尔排序方法又称为“缩小增量”排序。 该方法的基本思想是：先将整个待排对象序列 按照一定间隔分割成为若干子序列，分别进行 直接插入排序，然后缩小间隔，对整个对象序 列重复以上的划分子序列和分别排序工作，直 到最后间隔为1，此时整个对象序列已 “基本 有序”，进行最后一次直接插入排序
49 2516 08 2 = gap- 3目B 25 16103 49
21 25 49 25* 16 08 0 1 2 3 4 5 21 25* i = 1 08 49 gap = 3 25 16 49 25 16 08 49 25* 08 21 21 25 25* 16
2116 2525 49 08 2 5 i=2 8ap=2 自面目 25 16 {25 49
21 25 49 16 25* 08 0 1 2 3 4 5 21 i = 2 08 49 gap = 2 25 16 49 16 25* 08 21 25 49 25* 08 16 21 25* 25