[数据结构与算法]浅谈二分插入排序

二分插入排序，顾名思义，利用二分来完成排序

思路：假设前面所有元素已经排好顺序，本次要插入的元素大小为tmp，在前面已经排好顺序的所有元素中 利用二分找到大于tmp的第一个元素 假设位置为 k ，将 k 后面的所有元素向后移动一位，再将b[k]直接赋值为tmp，这些操作进行n次即可

图示：
利用二分找到大于tmp的第一个元素


代码实现：

#include<bits/stdc++.h>

using namespace std;

const int N=1000010;
int a[N],n,b[N];

void f(int x,int tmp){
	int l=1,r=tmp;
	while(l<r){
		int mid=l+r>>1;
		if(b[mid]>=x) r=mid;
		else l=mid+1;
	}
	for(int i=tmp+1;i>l;i--) b[i]=b[i-1];
	b[l]=x;
}

int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	b[1]=0x3f3f3f3f;
	for(int i=1;i<=n;i++){
		f(a[i],i);
	}
	for(int i=1;i<=n;i++) cout<<b[i]<<" ";
}

二分可以看这个以前的博客传送门