二分插入排序算法將時(shí)間復(fù)雜度降低到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;        
        }
}
程序源代碼：
//             本程序通過(guò)二分插入法實(shí)現(xiàn)對(duì)一組數(shù)據(jù)進(jìn)行升序排列

#include<iostream>
using namespace std;

void main()
{
 void paixu(int a[],int n);
 int *a;
 int n; 
 int q;
 int t=0;
     cout<<"本程序?qū)崿F(xiàn)二分插入排序。"<<endl;
     cout<<"請(qǐng)輸入待排序數(shù)據(jù)的個(gè)數(shù)："<<endl;
  cin>>n;
     a=(int*)malloc(sizeof(int)*n);                            //******************動(dòng)態(tài)分配所需數(shù)組空間**************
        cout<<"請(qǐng)輸入待排序數(shù)據(jù)： "<<endl;
       
     while(t<n)                                                   //**********從外界輸入待排序數(shù)據(jù)*****************
  { 
   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<<"排序后的數(shù)據(jù)為："<<endl;
 for(int p =0;p<n;p++)
   cout<<a[p]<<" ";
 cout<<endl; 
 }