折半插入排序 序子文件,我们可以采用折半查找法来确定R的插入位置,这种排序称为折半插入排序。其 算法可写出如下 void binarysort(struct node r[ n+ ll, int n) /*按关键字递增的次序对记录r[1]r(21…,rn进行折半插入排序* i for(F2 K<=n: 1++) r[o}=r[; h=i-I while(k=h) {mid=(+h)2 if(r[O). key<r[mid]. key) h=mid-1 else emid+I for(上1j=l-) r[=r[0; 在上面的算法中,每插入一个R1,平均比较次数为ogi折半插入排序 在线性插入排序中，我们采用顺序查找法来确定记录的插入位置。由于（R1，R2，…，Ri-1）是有 序子文件，我们可以采用折半查找法来确定R1的插入位置，这种排序称为折半插入排序。其 算法可写出如下： void binarysort(struct node r[ n+1],int n) /*按关键字递增的次序对记录r[1],r[2],……,r[n]进行折半插入排序*/ { for(i=2;i<=n;i++) { r[0]=r[i]; l=1; h=i-1; while(l<=h) { mid=(l+h)/2; if(r[0].key<r[mid].key) h=mid-1; else l=mid+1; } for(j=i-1;j>=l;j--) r[j+1]=r[j]; r[l]=r[0]; } } 在上面的算法中，每插入一个R1，平均比较次数为log2 i