直接插入排序中,前面的序列已经是有序的,需要找到当前需要插入的数在前面的数的位置,然后进行插入,直接插入排序采用从后往前依次找插入位置,如果前面的序列是有序表的话,可以用二分查找方法来找到要插入的位置。二分查找,设置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];
}
}
}
可见二分插入排序,只是减少了关键字之间的比较次数,并不能减少交换次数,只是在查找插入位置时提高了速度,而且必须是有序表的限制
*博客内容为网友个人发布,仅代表博主个人观点,如有侵权请联系工作人员删除。