[color=000000]请各位大虾讨论下两种折半插入算法的区别优劣


//这是由折半查找算法改成的折半插入算法。
template <typename T>
int OrderSearch(const vector<T> & a, const T & x)
{
 int low = 0;
 int high = a.size() - 1;
 int mid;
 int tem=x;
 
 while (low <= high)
 {
  mid = (low + high) / 2;
  
  if (a[mid] == tem)
   return mid+1;
   
  if (a[mid] < tem) //若a[mid] < x，则x位于 mid+1 ~ high 之间 
   low = mid + 1;
  else //若a[mid] >tem，则x位于 low ~ mid-1 之间 
   high = mid - 1;   
 }
 for (j=a.size() - 1; j>high; j--)//元素后移
                  a[j+1] = a[j];
            a[high+1] = tem; //插入
 }


//另外一种折半插入算法。
template <class T>
void HalfInsertSort(T a[], int len)
{
      int i, j;
      int low, high, mid;
      T temp;
      for (i=1; i<len; i++)
      {
            temp = a[i];
            low = 0;
            high = i - 1;
            while (low <= high) //在a[low。。。high]中折半查找有序插入的位置
            {
                  mid = (low + high) / 2;
                  if (a[mid] > temp)
                        high = mid - 1;
                  else
                        low = mid + 1;
            } //while
            
            for (j=i-1; j>high; j--)//元素后移
                  a[j+1] = a[j];
            a[high+1] = temp; //插入
      }//for
}[/color]