折半插入排序
也叫二分插入排序——插入排序的改进版
在插入排序的基础上改进而来，直接插入排序中，我们每次都要向前依次比较，二分插入法则在要插入的元素前通过二分折半搜索找到
插入地点，从而大大减小时间复杂度
时间复杂度：O(n*log2(n)) （直接插入排序是O(n^2), 可见有较大提升）
空间复杂度：O(1)
稳定性：稳定
1 public int[] binaryInsertSort(int[] a) { 2 3 for (int i = 1; i < a.length; i++) {//第i个元素为要向前插入的元素
4 //搜索部分 5 int left = 0; //左边边界 6 int right = i - 1; //右边边界 7 int temp = a[i]; 8 while (left <= right) { // 利用折半查找插入位置 9 int mid = (left + right) / 2; // 取中点 10 if (a[mid] > temp) // 插入值小于中点值，在前半部分 11 right = mid - 1; // 向左缩小区间 12 else //在后半部分 13 left = mid + 1; // 向右缩小区间 14 }
15 //移动部分 16 // left即为找到的要插入的位置，所以下边的循环将left-(i-1)位置的元素依次向后移动 17 for (int j = i - 1; j >= left; j--) { 18 a[j + 1] = a[j]; 19 } 20 a[left] = temp; // 插入 21 } 22 return a; 23 }