从上一小节可见，直接插入排序算法简便、容易实现。当待排序元素的数量 n 很小时，
这是一种较好的排序方法，但是通常待排序元素数量 n 很大，则不宜采用直接插入排序方法，
此时需要对直接插入排序进行改进。
直接插入排序的基本操作是向有序序列中插入一个元素，插入位置的确定是通过对有序
序列中元素按关键字逐个比较得到的。既然是在有序序列中确定插入位置，则可以不断二分
有序序列来确定插入位置，即搜索插入位置的方法可以使用折半查找实现。
折半插入排序的实现如代码。
算法binInsertSort
输入：数据元素数组 r，数组 r 的待排序区间[low..high]
输出：数组 r 以关键字有序
代码：
public void binInsertSort(Object[] r, intlow, int high){
for (int i=low+1;
i<=high;
i++){
Object temp = r[i];
//保存待插入元素
int hi = i-1;
int lo = low;
//设置初始区间
while (lo<=hi){//折半确定插入位置
int mid = (lo+hi)/2;
if(strategy.compare(temp,r[mid])<0)
hi = mid - 1;
else lo = mid + 1;
}
for (int j=i-1;
j>hi;
j--) r[j+1] = r[j];
//移动元素
r[hi+1] = temp;
//插入元素
}//for
}
从算法binInsertSort 容易看出，折半插入排序所需的辅助空间与直接插入排序相同，从时间上比
较，折半插入排序仅减少了元素的比较次数，但是并没有减少元素的移动次数，因此折半插
【android|java折半插入排序】入排序的时间复杂度仍为O(n 2 )。
