折半查找插入排序

本文将结合 二分查找 和 直接插入排序 的知识点，介绍折半查找插入排序

你可以通过点击以往文章回顾知识点:

点击 -> 二分查找

点击 -> 直接插入排序

算法思想

在维护一个有序序列的过程中，从左往右看，使用二分查找出第一个比 base 大的数的位置 l，然后将元素后移，在 l 处腾出空间，将 base 插入。

一个简单的例子：

算法模板

void binary_insert_sort(){
    // 维护一个有序序列
    for(int i = 1 ; i < n ; i++){
        // 相邻元素顺序情况
        if(q[i - 1] <= q[i]) continue;
        // 相邻元素逆序情况
        // 二分，从左往右找到第一个大于 base 的数
        int l = 0, r = i, base = q[i];
        while(l < r){
            int mid = l + r >> 1;
            if(q[mid] > base) r = mid;
            else l = mid + 1;
        }
        // 将 l 空出来
        for(int j = i - 1 ; j >= l ; j--)
            q[j + 1] = q[j]; // 元素后移，空出 l 这个位置
        // 插入
        q[l] = base;
    }
}