// 二分插入排序    // 分类 -------------- 内部比较排序    // 数据结构 ---------- 数组    // 最差时间复杂度 ---- O(n^2)    // 最优时间复杂度 ---- O(nlogn)    // 平均时间复杂度 ---- O(n^2)    // 所需辅助空间 ------ O(1)    // 稳定性 ------------ 稳定    public void insertionSortDichotomySolution(int[] arr) {        // 假设左边从0到i-1都已排好序        for (int i = 1; i < arr.length; i++) {            int current = arr[i];            int left = 0;            int right = i - 1;            int mid = (left + right) >> 1;            while (left <= right) {                if (arr[mid] > current) {                    right = mid - 1;                } else{                    left = mid + 1;                }                 mid = (left + right) >> 1;            }            for (int j = i - 1; j >= left; j--) {                arr[j + 1] = arr[j];            }            arr[left] = current;        }    }