算法介绍

算法介绍就是说我们原先写的插入排序的这段代码

for(int i=1;i<n;i++){//开始向前遍历，如果发现前面的元素比//x大的话，就将前面的元素放到x的后面int x = q[i],j=i;while( j && q[j-1]>x ){q[j] = q[j-1];j--;}q[j] = x;}

我们里面那层循环最坏的情况是比较N次，但是其实我们是可以通过二分来优化这一步骤的。但是我们也要明白二分只能优化比较次数，但是没办法优化换的次数。就是说因为原先已经进入新数组的排序顺序是已经有序的了，我们可以通过二分快速查找到我们需要插入的数的目标位置。

如下图

 注：y总的定义的区间都是左开右闭的

上面那里的代码也就替换成了下面这个

//i为啥从1开始？因为下标为0的数字没有位于其前需要比较的数for(int i=1;i<n;i++){//如果发现此时遍历的数本身就比前面最大的数大就不需要重排了if(q[i]>q[i-1]) continue;int x = q[i];//开始二分int left = 0, right = i-1;while(left<right){int mid = (left + right) >>1;//区间都是左开右闭的if(q[mid]>x) right = mid;else left = mid + 1;}//比x大的数全部往后移动一位for(int j = i-1;j>=right;j--){q[j+1] = q[j];}q[right] = x;}

算法题目

完整代码

#include <iostream>using namespace std;const int N = 1000010;
int q[N];
//区间都是左开右闭的
void discount_insert_sort(int n){//i为啥从1开始？因为下标为0的数字没有位于其前需要比较的数for(int i=1;i<n;i++){//如果发现此时遍历的数本身就比前面最大的数大就不需要重排了if(q[i]>q[i-1]) continue;int x = q[i];//开始二分int left = 0, right = i-1;while(left<right){int mid = (left + right) >>1;//区间都是左开右闭的if(q[mid]>x) right = mid;else left = mid + 1;}//比x大的数全部往后移动一位for(int j = i-1;j>=right;j--){q[j+1] = q[j];}q[right] = x;}return;
}
int main(){int n;cin>>n;for(int i=0;i<n;i++)scanf("%d",&q[i]);discount_insert_sort(n);for(int i=0;i<n;i++)printf("%d ",q[i]);return 0;
}