二分插入排序

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

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

 代码实现：

#include
using namespace std;
void mysort(int *a,int n)
{
    int left,right,mid;
    for(int i = 1;i < n;i ++)
    {
        left = 0;
        right = i - 1;//初始化left和right，使其每次循环都为边界值
        int x = a[i];
        while(left <= right)
        {
            mid = (left + right) / 2;
            if(a[i] > a[mid])
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        for(int j = i - 1;j >= left;j --)//left后面的数据全部后移一个位置
        {
            a[j + 1] = a[j];
        }
        a[left] = x;
    }
}
int main()
{
    int a[5] = {5 , 1 ,3 ,2 , 4};
    mysort(a,5);
    for(int i = 0;i < 5;i ++)
    {
        cout << a[i] << " ";
    }
    return 0;
}