插入排序的基本方法是：每步将一个待排序的元素，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。插入排序主要有直接插入排序、二分插入排序、希尔排序，本章主要介绍二分插入排序。

算法思想

在直接插入排序的基础上改进，将顺序比较改进为二分比较，如序列为1，4，7，2，8，此时遍历至i=3，即待排元素为2，直接插入是从已排序列向前逐一比较，2和7比较，2和7交换；2和4比较，2和4交换；二分插入是和已排序列的中间元素元素比较，2和4比较，2和1比较，最终2应该放在索引为1的位置，即元素4所在位置，然后将元素4，7向右移动一位，将2插入索引为1的位置

代码实现

public class BinaryInsertsort {
    public static void main(String[] args) {
        int[] array = new int[]{5,2,4,1,6,8,10,7,9,3};

        binaryInsertsort(array);

        for (int j : array) {
            System.out.println(j);
        }
    }

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

复杂度

时间复杂度

二分插入排序的比较次数少于直接插入排序，但移动次数和直接插入排序相同，平均为O(n²)

空间复杂度

O(1)，使用了一个额外空间存放temp值

稳定性

根据array[mid] == temp执行left = mid + 1可以看出插入位置为相等元素的右边，因此稳定

总结

排序算法	时间复杂度	空间复杂度	稳定性
二分插入排序	平均为O(n²)，优于直接插入排序	O(1)	稳定

插入排序之二分插入排序

Effy

算法思想

代码实现

复杂度

时间复杂度

空间复杂度

稳定性

总结

Other Articles

How to compile JDK in M1 MacBook——在M1上编译JDK

插入排序之直接插入排序