排序算法之折半插入排序

折半插入排序

    在直接插入排序的基础上做的改进,直接插入排序在寻找插入位置时是从后到前依次比较,直到找到插入位置。而折半插入排序在寻找插入位置时,先与有序序列中的中间位置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;
}
上一篇:排序算法之直接插入排序


下一篇:排序算法之直接选择排序