#include<iostream.h>//折半插入排序
#define MAX 4
void BinaryInsertSort(int a[],int N);//數(shù)組名稱,數(shù)組中元素個數(shù)
int main()
{ 
   int *p, i,n,a[MAX];
   n=MAX;
   p=a;

   cout<<"Input "<<n<<" number for sorting :"<<endl;
   for(i=0;i<MAX;i++)
   {
	 cin>>a[i];
   }
   cout<<endl;
   BinaryInsertSort(p,MAX);

   cout<<"After BinaryInsertSort:"<<endl;
   for(i=0;i<MAX;i++)
   {
     cout<<a[i]<<" ";
   }
   cout<<endl;
   return 0;
}

void BinaryInsertSort(int a[],int N)//折半插入排序
{

   for(int i=1;i<N;i++)
   {
     int temp=a[i];
	 int low=0,high=i-1;
     while(low<=high)//折半查找
	 {
       int mid=(low + high)/2;
       if(temp<a[mid]) 
		  high=mid-1; 
	   else 
		  low=mid+1;
	 }
     for(int j=i-1;j>=low;j--) 
	 {
		 a[j+1]=a[j];//記錄后移
	 }
     a[low]=temp;//插入	 
   }
}