2.折半插入排序
折半插入排序是对直接插入排序的一个改进，当数组元素较多时候，直接插入排序的效率不高.而折半排序能减少比较的次数，从而效率。我们来看看它是怎么减少比较次数的。
1.我们设3个变量low,high,mid,low为待比较的区间的最低位，high为待比较区间的最高位,mid为[low+mid]/2区间的中间位置.
2.我们比较中间位置和待插入元素的大小,若中间元素大于待插入元素那么只可能在中间元素的左边插入，我们令high=mid-1。若中间元素小于待插入元素，那么插入位置只可能在中间元素右边，此时我们令low=mid+1.
3.循环执行步骤2，直到low>high，此时high+1为插入的位置.我们再将high+1以后的元素依次后移，再将待插入的元素插入.
C:
void binsort(NODE a[],int n)
{ int low,high,mid,temp;
int i,j;
for(i=1;i<n;i++)
{ low=0;
high=i-1;
temp=a.key;
while(low<=high)
{ mid=(low+high)/2;
if(temp<mid) high=mid-1;
else low=mid+1;
}
for(j=i-1;j>=high+1;j--) a[j+1]=a[j];
a[j+1]=temp;
}
}
VB:
Private Sub binsort( a（） as NODE, n as long)
Dim low as long,high as long,mid as long,temp as long,i as long,j as long
for i=1 to n-1
low=0
high=i-1
temp=a(i）.key
Do While(low<high Or low=high)
mid=int((low+high)/2)
if temp<a（mid）.key then
high=mid-1
else
low=mid+1
end if
loop
for j=i-1 to high+1 step -1
a(j+1）=a（j）
next j
a（j+1)=temp
next i
End Sub
|
