折半插入排序 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 个frst8 数 据 结 构 之 内 部 排 序 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