二分插入排序算法将时间复杂度降低到n(n2)。
paixu(int a[], int n)
{
        int key, left, right, middle;
        for (int i=1; i<n; i++)
        {
                key = a[i];
                left = 0;
                right = i-1;
                while (left<=right)
                {
                        middle = (left+right)/2;
                        if (a[middle]>key)
                                right = middle-1;
                        else
                                left = middle+1;
                }
                
                for(int j=i-1; j>=left; j--)
                {
                        a[j+1] = a[j];
                }
                
                a[left] = key;        
        }
}
程序源代码：
//             本程序通过二分插入法实现对一组数据进行升序排列

#include<iostream>
using namespace std;

void main()
{
 void paixu(int a[],int n);
 int *a;
 int n; 
 int q;
 int t=0;
     cout<<"本程序实现二分插入排序。"<<endl;
     cout<<"请输入待排序数据的个数："<<endl;
  cin>>n;
     a=(int*)malloc(sizeof(int)*n);                            //******************动态分配所需数组空间**************
        cout<<"请输入待排序数据： "<<endl;
       
     while(t<n)                                                   //**********从外界输入待排序数据*****************
  { 
   cin>>q;
     a[t]=q;
     t++;
  }
  paixu(a,n);
}

 void paixu(int a[],int n)                                      //**************二分插入排序法的主体***************
 {
  int key, left, right, mid;
   for(int i=1; i<n; i++)                         
        {
                key = a[i];
                left = 0;
                right = i-1;
                while (left<=right)
                {
                        mid = (left+right)/2;
                        if (a[mid]>key)
                                right = mid-1;
                        else
                                left = mid+1;
                }
                
                for(int j=i-1; j>=left; j--)
                {
                        a[j+1] = a[j];
                }
                
                a[left] = key;       
        }
     cout<<"排序后的数据为："<<endl;
 for(int p =0;p<n;p++)
   cout<<a[p]<<" ";
 cout<<endl; 
 }