
void InsertSort ( S_TBL *s )
{ /* 对顺序表s 作折半插入排序*/
for ( i=2; i<=s->length; i++ )
{
s->elem[0]=s->elem[i]; /* 保存待插入元素*/
low=i;
high=i-1; /* 设置初始区间*/
while ( low<=high ) /* 该循环语句完成确定插入位置*/
{
mid= ( low+high ) /2;
if ( s->elem[0].key>s->elem[mid].key )
low=mid+1; /* 插入位置在高半区中*/
else high=mid-1; /* 插入位置在低半区中*/
}/* while */
for ( j=i-1; j>=high+1; j-- ) /* high+1 为插入位置*/
s->elem[j+1]=s->elem[j]; /* 后移元素,留出插入空位*/
s->elem[high+1]=s->elem[0]; /* 将元素插入*/
}/* for */
}/* InsertSort */



