java算法：折半插入排序

从无序序列中取出一个一个元素放入到一个有序序列中
把无序序列的第一个元素作为一个有序的序列，取下一个元素a，在有序序列中根据二分法，取出中间的元素b，a与b进行比较，若a大于b，则b在有序序列的后半部分，若a小于b，则在有序序列的前半部分，这样循环的的进行位置的确定，再把元素的插入到有序序列中正确的位置。

时间复杂度最好的情况为O(nlog2n),最坏的情况为O(n^2)

/**
     * 折半插入排序
     */
    public void insertSort03() {
        int[] arr = {3,2,6,1,7,5,9,8};
        for (int i = 1; i < arr.length; i++) {
            int insertValue = arr[i];//保存要插入的数的数值
            int low = 0;//设置查找区间初始值 下区间值
            int high = i - 1;//上区间值
            while (low <= high) {//查找结束条件
                int mid = (low + high) / 2;//折半，中间值
                if (arr[mid] > insertValue) {
                    //待插入值小于中间值
                    high = mid - 1;//上区间值变为中间值-1
                } else {
                    //待插入值大于中间值
                    low = mid + 1;//下区间值变为中间值+1
                }
            }
          
            for (int j= i-1; j >= low; j--){
                arr[j+1]=arr[j];//将low及low之前的数向前移动一位
            }
            arr[low]=insertValue;//low就是待插入值的适当插入点
        }

        Log.i(TAG, "折半插入排序结果："+ Arrays.toString(arr));
    }

折半插入排序结果：[1, 2, 3, 5, 6, 7, 8, 9]

参考：
https://blog.csdn.net/m0_37123168/article/details/121383070
https://blog.csdn.net/qq_57610796/article/details/122789713