直接插入排序中，前面的序列已经是有序的，需要找到当前需要插入的数在前面的数的位置，然后进行插入，直接插入排序采用从后往前依次找插入位置，如果前面的序列是有序表的话，可以用二分查找方法来找到要插入的位置。二分查找，设置low，high，当没有找到待插入元素时，=high的元素都是大于当前待插入元素的，所以找到了插入位置，即high之前。
代码如下：
[cpp] view plaincopy
/*
* 对sq+1,sq+2,...,sq+length进行二分直接插入排序
*/
void BinaryInsertSort(int *sq,int length){
int low,mid,high;
for(int i=2;isq[mid]){
low=mid+1;
}
else{
//有相同关键字
low=high=mid;
break;
}
}
printf("low=%d,high=%d\n",low,high);
int j;
for(j=i-1;j=high+1;j--){
sq[j+1]=sq[j];
}
sq[high+1]=sq[0];
}
}
}
可见二分插入排序，只是减少了关键字之间的比较次数，并不能减少交换次数，只是在查找插入位置时提高了速度，而且必须是有序表的限制
*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。
发布文章
