折半插入排序

时间复杂度: O(n^(3/2))

为维持折半插入排序的稳定性，让原本在前面的仍然在前面。所以默认当值相同时，让计算机当作“小”

else if(q[mid] <= t) l = mid + 1; 

参考讲解

https://www.bilibili.com/video/BV16d4y1r76N/?spm_id_from=333.337.search-card.all.click&vd_source=102f6911b86737e3cb7f0ed4fca03b11

C++代码

void binary_sort_insert(){

    for(int i = 1 ; i < n ; i ++){
        if(q[i-1] <= q[i]) continue;
        int t = q[i]; //保存暂存元素
        int l = 0, r = i-1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(q[mid] > t) r = mid - 1;
            else if(q[mid] <= t) l = mid + 1; //【注意】为了维持稳定性，让原本在前面的仍然在前面。所以默认当值相同时，让计算机当作“小”。
        }

        for(int j = i - 1; j >= l ; j --)
            q[j+1] = q[j]; 
        q[l] = t;
    }
}