折半插入排序

折半插入排序（binary insertion sort）是对直接插入排序的改进。在直接插入排序中，主要的时间消耗在数据的比较和移动上。那么有没有方法降低数据比较的次数呢？由于前半部分的序列已经有序，在为新数据寻找插入点时，可以采用折半查找的方法来提高寻找速度。

以数组arr[]为例，在将arr[]排列为一个降序序列的过程中，寻找插入点的具体操作是：

（1）分别使用low记录有序序列首位元素下标，high记录有序序列末尾元素下标，tmp记录待插入元素的数据；

（2）若low<=high，将arr[tmp]与arr[m]作比较，其中m=(low+high)/2：

a) 若tmp<arr[m]，使low=m+1；

b) 若tmp>=arr[m]，使high=m-1；

（3）重复步骤 (2)，直到low<=high不成立，此时找到插入点，其下标为high+1。

该过程与查找中的折半查找相同。以图1中的序列为例，演示折半查找的查找过程。其中arr[0]~arr[7]为有序序列，arr[8]~arr[9]为待排序序列。

图1 折半查找

（1）首先使low=0，high=7，则m=(low+high)/2=3，使用tmp记录arr[8]，tmp=7；

（2）比较tmp与arr[m]，tmp>arr[m]=4成立，使high=4-1=3，则m=(0+3)/2=1；

（3）low<=high成立，再次比较tmp与arr[m]=8，tmp<arr[m]，使low=m+1=2；

（4）low<=high依然成立，m=(low+high)/2=2，比较tmp与arr[m]，tmp>arr[m]，使high=2-1=1；

（5）此时low>high，所以插入点为下标为2的位置。

使用折半查找为本次插入寻找合适的插入点时，共进行了3次比较。若是使用直接插入排序，在本轮排序中，tmp需要依次与arr[7]~arr[0]的数据比较，7次比较过后，才找到合适的插入点。所以折半插入排序有效加快了寻找插入点的效率。但折半查找并非绝对提高寻找插入点的效率，对于一个本身有序的序列，反而直接插入排序效率更高。

折半插入中的核心是插入点的查找，若插入点为k，找到插入点后，将有序序列中插入点之后的数据依次后移一位，将新数据插入下标为k处。

使用折半插入排序的算法实现如下。

//折半插入排序
int BinarySort(int arr[], int n)
{
    int i, j;            //定义控制循环的变量
    int low, high, m;    //定义中间变量
    int tmp;
    for (i = 1; i < n; i++)    
    {
        tmp = arr[i];
        low = 0;
        high = i - 1;
        while (low <= high)    //寻找插入点
        {
            m = (low + high) / 2;
            if (tmp > arr[m])
                high = m - 1;
            else
                low = m + 1;
        }
        //移动有序序列中插入点之后的元素
        for (j = i - 1; j >= high + 1; j--)
            arr[j + 1] = arr[j];
        arr[high + 1] = tmp;    //将待排序数据插入有序序列
    }
}

折半插入排序节省了排序过程中比较的次数，但是移动的次数与直接插入排序相同，所以其时间复杂度仍为O(n2)。分析算法可知，在两个数据关键字相同时，不会交换数据顺序，所以该算法是一个稳定的算法。