文档介绍：数据结构与算法实验报告
实验名称： 二分插入排序及其性能
姓 名：
学 号：
专 业：
指导教师：
日 期： 2012-5-22
一、实验目的
了解二分插入排序与直接插入排序的关系； 掌握二分插入排序算
法的实现；掌握算法运行时间的测量。
二、实验内容
实现二分插入排序算法， 并将它和直接插入排序算法进行性能比
较，然后用理论分析支持你的结论。
三、实验环境
Window XP操作系统；
Microsoft VisualC++ 编程环境；
Pentium(R) Dual-Core cpu;
, 内存
四、实现
提示：总排序类、插入排序类、直接插入排序类、二分插入排序
类间的关系
答：父类是：总排序类
子类是：插入排序类 和二分插入排序类
父类是：插入排序类
子类是：直接插入排序类
sort 的实现
结果：
//二分法插入排序， Array[] 为待排序数组， n 为数组长度
template <class Record,class Compare>
void BinaryInsertSorter<Record,Compare>::Sort(Record Array[], int n)
{
Record TempRecord; //用来保存当前待插入纪录的临时变量
int left,right,middle; //记录已排好序序列的左、右、中位置
for (int i=1;i<n;i++) //插入第 i 个记录
{
TempRecord = Array[i]; // 将当前待插入记录保存在临时变量中
left = 0; right = i-1; // 记录已排好序序列的左右位置
while(left <= right) // 开始查找待插入记录的正确位置
{
middle = (left+right)/2; //记录中间位置
//如果待插入记录比中间记录小，就在左一半中查找，否则，在右一半中查找
if (Compare::lt(TempRecord, Array[middle]))
right = middle-1;
else left = middle+1;
}
//将前面所有大于当前待插入记录的记录后移
for(int j = i-1; j >= left; j --)
A