折半插入排序( 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] 的插入位置
折半插入排序的算法 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 L rhigh+1=Lr[01; 说明: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为插入点 稳定排序
算法分析 对分查找比顺序查找快,所以对分插入排序 就平均性能来说比直接插入排序要快 它所需要的关键字比较次数与待排序对象序 列的初始排列无关,仅依赖于对象个数。在 插入第i个对象时,需要经过Llg2i+1次关 键字比较,才能确定它应插入的位置。因此, 将n个对象(为推导方便,设为n=2k)用对分 插入排序所进行的关键字比较次数为
算法分析 对分查找比顺序查找快，所以对分插入排序 就平均性能来说比直接插入排序要快。 它所需要的关键字比较次数与待排序对象序 列的初始排列无关，仅依赖于对象个数。在 插入第 i 个对象时，需要经过 log2 i +1 次关 键字比较，才能确定它应插入的位置。因此， 将 n 个对象（为推导方便，设为n=2k )用对分 插入排序所进行的关键字比较次数为：
∑(bog2{」+1)=!+2+2+3+…+3+ +4+∵+4+·十k++k= (1+2+22+…+2k-)+(2+22+…+2k-)+ +(22+…+2)+ +2 kk k ∑∑2=∑2-(1+2+…+2-) k k k ∑2(2 k-i+1 ∑2-∑2 k. 2-(2-1)=nlog n-n+la n log n
( ) k n n n n n k k i k k k i i k i k i k k i i k i i k i k i k j i j k k k k n i k 2 2 1 1 1 1 1 1 1 1 1 1 2 1 1 2 1 2 1 2 2 2 2 2 1 1 2 2 (2 1) log 1 log 2 (2 1) 2 2 2 2 (1 2 2 ) (2 2 ) 2 (1 2 2 2 ) (2 2 2 ) 4 4 log 1 1 2 2 3 3 3 1 0 1 2 = − − = − + = − = − = = = + + + = + + + + + = = + + + + + + + + + + + + + + + + = + = + + + + + + = − = − + = − = − − = = − − − − − − = −
当n较大时,总关键字比较次数比直接插入 排序的最坏情况要好得多,但比其最好情况 要差 在对象的初始排列已经按关键字排好序或接 近有序时,直接插入排序比对分插入排序执 行的关键字比较次数要少。对分插入排序的 对象移动次数与直接插入排序相同,依赖于 对象的初始排列。 对分插入排序是一个稳定的排序方法
当 n 较大时，总关键字比较次数比直接插入 排序的最坏情况要好得多，但比其最好情况 要差。 在对象的初始排列已经按关键字排好序或接 近有序时，直接插入排序比对分插入排序执 行的关键字比较次数要少。对分插入排序的 对象移动次数与直接插入排序相同，依赖于 对象的初始排列。 对分插入排序是一个稳定的排序方法