-
程序:
void BInsertSort(SqList &L)
{ // 对顺序表L作折半插入排序。算法10.2
int i,j,m,low,high;
for(i=2;i<=L.length;++i)
{
L.r[0]=L.r[i]; // 将L.r[i]暂存到L.r[0]
low=1;
high=i-1;
while(low<=high)
{ // 在r[low..high]中折半查找有序插入的位置
m=(low+high)/2; // 折半
if LT(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]; // 插入
}
}
-
总结:此方法和直接插入排序所需的辅助空间相同,从时间上比较,仅减少了关键字比较的次数,记录的移动次数不变。所以,时间和空间复杂度都和直接插入排序相同。
-
思想:在1到i-1的子序列中寻找插入的位置是采用折半查找。
评论