binaryinsertsort.h

随机产生个整数n=100

template<class T>
void BinaryInsertSort(T a[],int N,int&KCN,int&RMN)
{
    KCN=0 ;
    RMN=0 ;
    for(int i=1;i<N;i++)
    {
        T temp=a[i];
        RMN++;
        int low=0,high=i-1 ;
        //折半查找
        while(low<=high)
        {
            int mid=(low+high)/2 ;
            if(++KCN&&temp<a[mid])high=mid-1 ;
            else low=mid+1 ;
        }
        for(int j=i-1;j>=low;j--)
        {
            a[j+1]=a[j];
            RMN++;
        }
        //记录后移
        a[low]=temp ;
        RMN++;
        //插入
    }
}