1、快速排序(手写)

最优时间复杂度O(n log n)
最坏时间复杂度O( n^2 );

每次找出一个哨兵数flag

用2个指针i,j , i表示小于flag的数，j表示大于flag的数

当i,j指向的数不合法是就把他们交换,直到j >= i;

然后递归处理就可以

代码
https://www.acwing.com/activity/content/code/content/9330850/

细节

由于用了do while语句 ，所以i初始成l - 1,j初始成r+1;

然后这里的flag要取中间值,否则时间复杂度更容易到O(n^2)

2、位运算

常用操作(x >> k) & 1 , lowbit(x);

注意：二进制的位数从0开始计数

x右移k位就是把第k位的值放到第0位，然后用这一位与1就能判断这一位是否是1;

lowbit(x)就是(x & -x)用于取x最低的一位1

-x的值是取反x加1

举例：
x = 100010;
~x= 011101;
-x = ~x + 1 = 01111;(因为进位)

由于前面的都是取反的结果，所以都是0不用管，而取反x加一会把最低的0位变成1，正好这一位原来是1，所以lowbit操作就能取出最低的1;

3、区间合并

把几个有重复的区间合并成1个区间，就是区间合并

首先按左端点排序

然后考虑3种情况

1、区间x包含区间y;
2、区间x和区间y无交集
3、区间x和区间y有交集

第一种情况不用管，第二种情况直接把当前区间加入答案列表，第三种令区间x的末尾位y的末尾即可

代码
https://www.acwing.com/activity/content/code/content/9345217/

4、高精度

思路还是模拟竖式，这里提供精简实现

高 + 高
https://www.acwing.com/activity/content/code/content/9334011/

高 - 高
https://www.acwing.com/activity/content/code/content/9334196/

高高 && 高低
https://www.acwing.com/activity/content/code/content/9334244/

高/低
https://www.acwing.com/activity/content/code/content/9334286/

5、二分

先看2个模板
https://www.acwing.com/blog/content/31/

整数二分的本质

定义一个性质在右边区间满足，左边不满足，然后就可以二分出2个区间的边界

怎么找到左边区间的边界：
mid = (l+r+1)/2 , if ( check(mid) )
(mid取值一会详细解释)

如果这个判断为true，答案会在[mid,r]因为mid可能是边界点
l = mid;

如果这个判断为false，那么mid不满足check,那么mid就是满足这个性质的，在右边边区间

答案是[l,mid-1],因为mid,和比mid大的数都在合法区间内
r = mid - 1;

怎么找到右边区间的边界：
mid = (l+r) / 2 , if( check(mid) )

如果是check(mid) = true ， 那么查询区间变成[l,mid]
r = mid;

否则，查询区间是[mid + 1,r]
l = mid + 1;

为什么要加1

如果l = r - 1;

mid如果不加1，并且check(mid)成立，那么直接除法(下取整)
会把mid = l , 就陷入了l = mid = l的死循环，所以+1上取整

具体做题时不需要考虑这么多，可以随便写一个check,然后根据check值思考怎么划分，如果是第一种把mid值补上1

然后最后的结果是l,r还是其他可以用画图

https://www.acwing.com/activity/content/code/content/9333548/