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
|
