Java排序算法详解—— 二分插入排序

　　二分插入排序Binary Insert Sort

　　概念：

　　二分(折半)插入排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接排序算法最大的区别在于查找插入位置时使用的是二分查找的方式，在速度上有一定提升。

　　原理：

　　总共有N个元素，当插入第i个元素时，对前面的0~i-1个元素进行折半，先跟他们中间的那个元素比，如果小，那么再对前半折半，否则对后半进行折半，知道左右，然后再把第i个元素前一位于目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

　　关说原理可能大家不是很理解，下面我们就用一个列子来详细说明一下：

　　例如：我们当前数组为[4 5 7 10 29 11]

　　已知当前0到第N-1个都是按顺序排序，现在对第N个11找对应位置。

　　第一趟

　　11比中间M大

　　那么接下来第二趟为：

　　11比中间M大

　　那么11的位置就在M+1这个

　　注意，我们这里的第0到第N-1已经是按照要求排好序的

　　代码：