程序： 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的子序列中寻找插入的位置是采用折半查找。

评论