二分插入排序

1.算法思想

二分插入排序也是插入排序算法的一种，其基本思想是：引入二分查找的思想，在直接插入排序的基础上减少比较次数，从而更快的找到插入位置。

2.算法图解

最后一个待排序元素通过二分插入算法找到自己的位置并插入其中，初始状态左边界为0，右边界为6，mid=3，中间值为49，最后一个元素不小于49则左边界扩大为mid+1=4，mid=5，此时中间值为76，最后一个元素小于76则右边界缩小为mid-1=4，mid=4，此时中间值为65，最后一个元素小于65则右边界缩小为mid-1=3，找到了插入位置，即左边界位置为插入位置，其后的元素全部后移。

3.算法实现

• 以下为C语言代码实现：

/*
二分插入排序算法（升序）
 */
#include<stdio.h>
#include<stdlib.h>

void binSort(int *a,int len);
void binSort(int *a,int len)
{
    int mid,left,right,temp;
    for(int i=1;i<len;i++)
    {
        left = 0;//初始化已拍好序的左边界为0
        right = i-1;//右边界为待排序元素的前一个位置
        temp = a[i];//待排序元素
        while(left<=right)
        {
            mid = (left+right)/2;//计算中间位置
            if(temp<a[mid])
            {
                right = mid-1;//如果比中间位置小则缩小右边的范围为mid-1
            }
            else
            {
                left = mid+1;//如果比中间位置大则扩大右边的范围为mid+1，
            }
        }
        for(int j=i-1;j>=left;j--)
        {
            a[j+1] = a[j];//将大于等于左边界值的元素全部后移
        }
        if(left!=i)
        {
            a[left] = temp;//待插入元素插入位置不等于现在所处位置时，则插入空处
        }
    }
}

int main()
{
    int a[]={49,38,65,97,76,13,27,49};//待排序数组
    int len = sizeof(a)/(sizeof(a[0]));
    binSort(a,len);
    for(int i=0;i<len;i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

• 以下为Java代码实现：

package binarySort;
public class BinarySort {

    public static void sort(int a[])
    {
        int temp,left,right,mid;
        for(int i=1;i<a.length;i++)
        {
            temp = a[i];
            left = 0;
            right = i-1;
            while(left<=right)
            {
                mid = (left+right)/2;
                if(temp<a[mid])
                {
                    right = mid-1;
                }
                else 
                {
                    left = mid+1;
                }
            }
            for(int j=i-1;j>=left;j--)
            {
                a[j+1] = a[j];
            }
            if(i!=left)
            {
                a[left] = temp;
            }
        }
    }
    public static void main(String agrs[])
    {
        int []a = {49,38,65,97,76,13,27,49};
        BinarySort.sort(a);
        for(int element :a)
        {
            System.out.print(element+" ");
        }
    }
}

4.小结

二分插入排序算法是对直接插入排序算法的一种改进，通过引入二分查找算法减少比较次数从而提高算法效率，二分插入排序算法的平均时间复杂度为T(n)=O(n^2)，算法的辅助空间为S(n)=O(1)，算法中通过right<left来控制二分查找的结束，以temp<a[mid]为稳定控制条件，所以二分插入排序算法是稳定的。
如有不正确的地方请大神指正，谢谢大家！