一、快速排序
1、快速排序算法模板
🔺记忆！
void quick_sort(int q[], int l, int r) { //递归的终止情况 if (l >= r) return; //选取分界线。这里选数组中间那个数 int i = l - 1, j = r + 1, x = q[l + 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]); } //对左右部分排序 quick_sort(q, l, j), quick_sort(q, j + 1, r); }
2、边界问题
边界问题只有这两种组合，不能随意搭配，要对称着写。
// 1. x不能取q[l]和q[l+r>>1]; 取q[r]或q[(l+r+1)>>1] quick_sort(q,l,i-1),quick_sort(q,i,r); // 2. x不能取q[r]和q[(l+r+1)>>1]; 取q[l]或q[l+r>>1] quick_sort(q,l,j),quick_sort(q,j+1,r);
假设 x = q[l]; quick_sort(q, l, i-1); quick_sort(q, i, r);
取一个样例：q = [1, 2]
那么 l = 0, r = 1;
则 x = q[0] = 1; qucik_sort(q, 0, -1); quick_sort(q, 0, 1);
第一个快排不符合条件，结束。第二个快排进入死循环。
其他边界问题同理，会进入死循环。
3、注意事项
（1）i = l-1, j = r+1;
为什么这里不是 i = l, j = r 呢？
因为后面用的是 do-whlie 循环，先进行循环体里面的内容，再来判断条件。因此 i，j 的初始位置分别位于 l，r 的两侧。
因为两个指针在每次交换完之后都需要向中间移动一位，所以可以每次上来就先移动一次，这样我们就需要把指针的初始值放到外侧。
（2）swap() 函数
如果不直接使用 swap 函数，也可以自己手写一个。
if (i < j) { int k = q[i]; q[i] = q[j]; q[j] = k; }
注意：在交换前，要先进行条件判断，确保 i 和 j 在交汇之前不会越界。
（3）do-while循环的条件
为什么这里 do-while 循环的条件不能写成 q[i] <= x 和 q[j] >= x？
do-whlie 循环中的条件不能带等号，如果加上等号可能会导致下标增加到 r+1，从而导致数组越界。
（4）if 条件
if (i < j) 能否改成 if (i <= j)？
if (i < j) 条件中可以加上等号，因为 i == j 时表示自己与自己交换，因此没有任何影响。
4、练习
二、归并排序
1、归并排序算法模板
🔺记忆！
void merge_sort(int q[], int l, int r) { //递归的终止情况 if (l >= r) return; //第一步：分成子问题 int mid = l + r >> 1; //第二步：递归处理子问题 merge_sort(q, l, mid); merge_sort(q, mid + 1, r); //第三步：合并子问题 int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else tmp[k ++ ] = q[j ++ ]; while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ]; //第四步：复制回原数组 for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; }
2、注意事项
（1）移动
当两个序列当前指针对应的元素相等时，应该移动哪一个？
虽然说移动哪一个指针都可以，但是我们一般会选择移动第一个序列的指针。因为这样可以保持排序的稳定性。即保持序列中相同值在排序之后顺序不变。
（2）划分点的选取
为什么划分点为 mid ，而不是 mid-1？
因为 mid = (l+r) >> 1 是向下取整的，可能会取到 l。假设第一个递归范围是 [l，mid-1]， 则第二个递归是 [mid，r]，这就造成了当 mid 取到 l 时会无限划分，进入死循环。使用 mid 作为划分点不会造成无限划分，原因是两个范围 [l，mid]，[mid+1，r]，mid 是向下取整，所以不可能取到 r，因此不会出现 [l，r] 的情况，就不会产生无限划分。如果真的想要使用 mid-1 作为划分点，我们只需要让 mid 向上取整即可。即 mid = (l+r+1) >> 1。但实际上并不建议这样去写，因为判断条件会变成 while (i < mid && j <= r) 或者 while (i <= mid-1 && j <= r)，这两种写法都不对称，不利于记忆，所以还是建议划分点选择 mid。
3、练习
三、二分
1、整数二分算法模板
对 lower_bound 来说，它寻找的就是第一个满足条件 “ 值大于等于 x” 的元素的位置；对 upper_bound 函数来说，它寻找的是第一个满足 “ 值大于 x” 的元素的位置。
🔺记忆！
bool check(int x) {/* ... */} // 检查x是否满足某种性质 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1;//左加右减 } return l; } // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用： int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1;//如果下方else后面是l则这里加1 if (check(mid)) l = mid; else r = mid - 1;//左加右减 } return l; }
- 当我们将区间 [l，r] 划分成 [l，mid] 和 [mid+1，r] 时，其更新操作是 r = mid 或者 l = mid + 1;，计算 mid 时不需要加 1。
- 当我们将区间 [l，r] 划分成 [l，mid-1] 和 [mid，r] 时，其更新操作是 r = mid - 1 或者 l = mid;，此时为了防止死循环，计算 mid 时需要加 1。
【注意事项】
（1）模板选取
该如何确定用哪个模板呢？
取决于 check 的逻辑，如果我们发现需要更新区间为 [l，mid] 或 [mid + 1，r]，就用第一个模板。如果我们发现我们需要更新区间为 [l，mid - 1] 或 [mid，r]，就用第二个模板。
（2）mid 的选取
当左边界l 和 r 相距一个元素时，就是如果 l = r-1；也就是说 l 和 r 之间只相差 1 时，如果模板 2 中 mid = l + r >> 1; 那么通过向下取整，也就是 mid = (l + l + 1) >> 1; 可以得到 mid = l。假设 check 为 true，那么 l = mid = l; 判断结束后，l 和 r 都没作改变，就会陷入死循环。所以这里使用模板 2 必须得 + 1。
2、浮点数二分算法模板
🔺记忆！
bool check(double x) {/* ... */} // 检查x是否满足某种性质 double bsearch_3(double l, double r) { const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求 while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; }
【注意事项】
（1）精度
除了精度以外，还有其他表示方法吗？
可以写一个 for 循环，迭代 100 次，效果一样。
for (int i=0; i<100; i++) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; }
（2）eps 的选取
如果题目要求保留 4 位小数，eps = 1.e-6。如果保留 5 位小数，eps = 1.e-7。这样可以保留一个经验值，其他情况以此类推。
（3）mid 的选取
mid = l+r >> 1; 能否改成 mid = (l+r)/2; ？
这里的 mid 最好不要写成 l+r >> 1，因为 l+r >> 1 是将 l+r 右移一位，相当于除以 2，但在这里，我们需要计算 (l+r)/2，这个操作会进行向下取整，而右移操作会直接截断小数部分而不是四舍五入，所以可能会对精度产生影响。
