「Algorithm」01 基础算法
第一章 基础算法 包括排序,二分,高精度,前缀和与差分,位运算,离散化,区间合并 消除同步 ios::sync_with_stdio(false);//让cin和标准输入输出不同步,提高cin的读取速度,不能再使用scanf和printf了。 scanf/getchar和cin不要一起用,printf/puts/putchar和cout不要一起用。 可以使用freopen 还可以加上 cin.tie(0) 来解除c++运行库层面的对数据传输的绑定。 排序 1. 快速排序 基于分治。 确定一个分界点,比如(以1开始),取q[1],q[(1+r)/2] ,q[r], 随机为x 调整区间,小于等于x的在左边,大于等于x的在右边。等于x的可以在左边也可以在右边,也可以在边界上,不稳定。 递归处理左右两段。 方法一: 开两个额外的数组,a[],b[] 扫描q数组,如果q[i] ≤ x,存入a,如果q[i]>x,存入b。 然后将a数组的数存入q,b数组的数存入q。 方法二: i和j指针,i指向初始,j指向末尾。然后i向右走,直到遇到一个大于x的数。j向左走,直到遇到一个小于等于x的数。然后交换,直到 j ≤ i. 模板: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include <iostream> using namespace std; const int N = 1e6 + 10; int n; int q[N]; void quick_sort(int q[], int l, int r) { if (l >= r) return; int x = q[(l+r) >> 1], i = l - 1, j = r + 1; while( i < j){ do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j ) swap(q[i],q[j]); } //j可能比i小,也可能等于i。 quick_sort(q, l, j); //也可以换成 l, i -1 quick_sort(q, j + 1, r); //换成 i, r //后来说明不能换成i,因为也是会出现死循环问题。 //遇到这种情况,就考虑0,1。 //用j的话,x不能取右边界,(j可以取q[l]、q[(l+r)/2]) //j不能取 q[r]、q[(l+r+1)/2] //用i的话,x不能取左边界。 (i可以取q[r]、q[(l+r+1)/2]) //i不能取 q[l]、q[(l+r)/2] } //当下面换成i,r时,不能取x=q[l],因为会出现死循环的问题。比如排序1,2 //i最终为0,j也是0,这样使用quick_sort()会死循环。 //同理,如果取j+1,r,不能取右边界。 int main(){ scanf("%d",&n); for(int i = 0; i < n; i ++ ) scanf("%d",&q[i]); quick_sort(q,0,n-1); for(int i = 0; i < n; i ++ ) printf("%d ",q[i]); return 0; } 排序的话,可以使用 #include<algorithm> sort(q, q+n); 2....