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

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

总共有N个元素，当插入第i个元素时，对前面的0~i-1个元素进行折半，先跟他们中间的那个元素比，如果小，那么再对前半折半，否则对后半进行折半，知道左<右，然后再把第i个元素前一位于目标位置之间的所有元素后移，再把第i个元素放在目标位置上。
关说原理可能大家不是很理解，下面我们就用一个列子来详细说明一下：

例如：我们当前数组为[4 5 7 10 29 11]
已知当前0到第N-1个都是按顺序排序，现在对第N个11找对应位置。
第一趟

[4 5 7 10 29] 11  
L    M     R

11比中间M大
那么接下来第二趟为：

[4 5 7 10 29] 11
     L  M  R

11比中间M大
那么11的位置就在M+1这个

//从小到大
 public  void sort() {
 for (int i = 1; i < array.length; i++) {
     int temp = array[i];
     int low = 0, high = i - 1;
     int mid = -1;
     while (low <= high) {
  mid = low + (high - low) / 2;
  if (array[mid] > temp) {
      high = mid - 1;
  } else { // 元素相同时，也插入在后面的位置
      low = mid + 1;
  }
     }
     for(int j = i - 1; j >= low; j--) {
  array[j + 1] = array[j];
     }
     array[low] = temp;
 }
    }

冒泡排序
选择排序
直接插入排序
二分插入排序
希尔排序
堆排序
快速排序

Java和Kotlin代码我均放在了GitHub上，欢迎Star！