l9_2.cpp

数据结构课程的源代码

//二分插入排序
#include<iostream.h>
typedef int ElemType;
const int n=10;
ElemType a[n]={2,6,4,8,10,7,1,5,3,9};
void BinaryInsertSort(ElemType R[],int n)
{
  for(int i=1; i<n; i++)  //i表示插入次数，共进行n-1次插入
  {
	  int left=0,right=i-1;ElemType temp=R[i];
    while(left<=right)
	{
       int middle=(left+right)/2;      //取中点
       if(temp<R[middle])
         right=middle-1;               //取左区间
       else 
		   left=middle+1;            //取右区间
	}
     for(int j=i-1;j>=left;j--)
	 R[j+1]=R[j];                 //元素后移空出插入位
	  R[left]=temp;
  }
}

void print(ElemType r[n])
{ int i;
for(i=0;i<n;i++)
cout<<r[i]<<" ";
cout<<endl;
}
void main()
{ cout<<"排序前的结果为:"<<endl;
print(a);
 BinaryInsertSort(a,n);
cout<<endl<<"排序后的结果为:"<<endl;
print(a);
}