1template<class Type>
2void BinaryInsertSort(datalist<Type> &list){
3    for(int i=1;i<list.CurrentSize;i++) BinaryInsert(list,i);
4};
5
6template<class Type>
7void BinaryInsert(datalist<Type> &list){
8//利用折半查找，按list.Vector[i].key在list.Vector[0]到list.Vector[i-1]中
 9//查找list.Vector[i]应插入的位置，再空出这个位置进行插入。
10    int left=0,right=i-1;
11    Element<Type> temp = list.Vector[i];
12    while(left<=right){//利用折半查找插入位置
13        int middle = (left+right)/2;//取中点
14        if(temp.getKey()<list.Vector[middle].getKey())//插入值小于中点值
15            right = middle - 1;//向左缩小区间
16        else left = middle + 1;//否则，向右缩小区间
17    }
18
19    for(int k=i-1;k>=left;k--) list.Vector[k+1]=list.Vector[k];//成块移动空出插入位置
20    list.Vector[left]=temp;//插入
21};