折半插入排序

折半插入排序是对直接插入排序的改进，直接插入排序是需要将待插入数据和之前序列中的每一个元素进行比较，找到插入点，但是待插入元素之前的元素已经是有序的，我们可以利用这个有序表，进行二分法找到插入的位置，这样可以减少比较的次数。但是没有减少元素的移动次数，所以排序的时间复杂度没有大的变化，基本和直接插入排序保持一致

public static void insertsort(int[] arr) {  
    for(int i=1;i<arr.length;i++) {
        int temp = arr[i];
        int left = 0;
        int right = i-1;
        while(left<=right) {
            int mid = (left+right)/2;
            if(temp>arr[mid]) {
                left = mid+1;   
            }
            else {
                right = mid-1;
            }   
        }
        
        for(int j = i-1;j>right;j--) {
            arr[j+1] = arr[j];
        }
        arr[right+1]=temp;
        
    }
}

public static void main(String[] args) {
    int[] arr = {15,23,12,4,51,4,12,45};
    insertsort(arr);
    System.out.println(Arrays.toString(arr));
}