菜鸟学排序:折半插入排序

与直接插入排序思路相似,也是先将a[0]视为单独有序,只不过查找插入点的方法不再是与有序数组最后一个数进行比较,而是使用折半查找。

比如现有有序数列:1,2,4,6,8,欲插入数7,则现将7与中间位置的数4比较,大于4,则说明插入点应该在后半区6,8 ,由于后半区个位为偶,这里取前一位6进行比较,大于6,则说明插入点在后半区数列8前后,与8比较,小于8,则插入点在8之前。

总之,就是将有序数列划分为前半区和后半区,将插入数与有序数列中间数比较,判断插入点是在前半区还是后半区,接着在相应区进行递归即可。

实现代码如下:

//折半查找 只能在有序数列中进行查找  
int binarySearch(int a[],int low,int high,int key)  
{  
    if (low < high) {  
        return low;  
    }  

    int mid = (low + high)/2;  
    if (a[mid] == key) {  
        return mid;  
    }  
    else if (a[mid] < key)  
        return binarySearch(a, mid+1, high, key);  
    else  
        return binarySearch(a, low, mid-1, key);  
}  

//折半插入排序  
void binaryInsertSort(int a[],int length)  
{  
    int i,j;  
    int loc;  
    int temp;  
    for (i = 1; i < length; i++) {  
        loc = binarySearch(a, 0, i, a[i]);    //a[i]查找要插入的位置  
        temp = a[i];  
        for (j = i; j > loc; j--) {         //移位  
            a[j] = a[j-1];  
        }  
        a[loc] = temp;  

    }  
}