#include<iostream.h>
#include<iomanip.h>
void Binsertsort(int A[],int n)
{
	int i,j,low,high,mid,x,p;
	for(i=1;i<n;i++)
	{
		low=0;high=i-1;
		x=A[i];
		while(low<=high)
		{
			mid=(low+high)/2;
			if(x<A[mid])
				high=mid-1;
			else
				low=mid+1;
		}
		p=low;
		for(j=i-1;j>=p;j--)
			A[j+1]=A[j];
		A[p]=x;
	}
}
void main()
{
	int A[10],s,n=10;
	cout<<"請輸入要求排序的無序序列(10個數據):";
	for(s=0;s<n;s++)
		cin>>A[s];
	cout<<"折半插入排序"<<endl<<"排序前:";
	for(s=0;s<n;s++)
		cout<<setw(3)<<A[s];
	cout<<endl;
	Binsertsort(A,n);
	cout<<"排序后:";
	for(s=0;s<n;s++)
		cout<<setw(3)<<A[s];
	cout<<endl;
}