//折半插入排序
//联系，优化查找，利用折半找到位置，然后统一移动
//虽然优化了查找，但是移动没有变化
//反而最好情况下，也要一直去查找

include[HTML_REMOVED]

using namespace std;

void bin_insertsort(int data[],int n){
int low=1,high=n;
for(int i=2;i<=n;i++){
data[0]=data[i];//这里是暂存，不是哨兵
low=1,high=i-1;
while(low<=high){//折半查找子问题，只要low<=high就能继续
int mid=(low+high)/2;
if(data[mid]==data[0]) low=mid+1;
//即使查找到了，low还是+1，low最终指向我插入位置
//根据分块可知，low最终指向位置大于等于我，这里等于low向后
//所以最后low指向位置大于我
if(data[mid]>data[0]) high=mid-1;
if(data[mid][HTML_REMOVED]=low;j–)//这里假设只移动前面一个元素
data[j+1]=data[j];
data[low]=data[0];
}
}

int main()
{
int data[]={100,1,3,5,7,9,2,4,6,8,0};
for(int i=1;i<=10;i)
cout<<data[i]<<’ ‘;
cout<<endl;
bin_insertsort(data,10);
for(int i=1;i<=10;i)
cout<<data[i]<<’ ‘;
}

//分析
//这里二分查找一定会失败，所以到达失败结点，前面有n个结点，比较logn次
//这里应该和初始状态无关，比较次数固定（和简单选择很类似）n个结点平均nlogn次
//如果是有序情况，仍然会比较很多次，直接插入才比较n-1次，最好情况下不如直接插
//这里不需要移动，所以复杂度nlogn。而且是固定的吧

//最坏情况下，比较次数会减少很多
//但是移动是没有变化的，所以依然是n²

//空间O(1)
//适合n比较小，元素基本有序不如直接插
//稳定，data[mid]=data[0] low=mid+1

//这里使用了随机存储，所以链式不能用