折半插入排序
在直接插入排序的基础上做的改进,直接插入排序在寻找插入位置时是从后到前依次比较,直到找到插入位置。而折半插入排序在寻找插入位置时,先与有序序列中的中间位置R[mid]进行比较,如果比中间位置上的记录大,则在R[mid+1…N]中寻找,继续与右区间的中间记录进行比较;如果比中间位置上的记录小,则在R[0…mid-1]中寻找,继续与左区间中的数据进行比较。
typedef int datatype;
int BinaryInsertionSort(datatype *array, int size)
{
int i, j, low, high, mid;
int temp;
if(array == NULL) {
return -1;
}
for(i = 1; i < size; i++) {
low = 0;
high = i-1;
temp = array[i];
//跳出循环时low为插入位置
while(low <= high) {
mid = (low + high) / 2;
//若比中间记录小,则去左区间查找
if(array[mid] > temp) {
high = mid - 1;
} else {
//否则去右区间查找
low = mid + 1;
}
}
//将插入位置到待插入元素的位置上的元素整体向后移动一个位置
for(j = i; j > low; j--) {
array[j] = array[j-1];
}
array[low] = temp;
}
return 0;
}