目录
一. 快速排序
二. 归并排序
三. 二分
✨整数二分：
✨浮点数的二分
四. 前缀和
✨ 一维前缀
✨二维前缀
五. 差分
一. 快速排序
快速排序：（分治的思想）✅
确定分界点：q[l], q[(r+l)/2], q[r] (中间点可以随机选, 按照同一规则, 这里选(l+r)/2该点)
维护数组：维护分界点的左边都比分界点小，分界点的右边都比分界点大
按照维护关系, 递归处理左右两段
💡思想解释:
先整后细：先让大体总的符合条件，再部分部分解决
模板代码
void quick_sort(int q[], int L, int R){ if(L >= R) return; int x = q[L], 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]); } quick_sort(q, L, j); quick_sort(q, j + 1, R); }
🌸代码解析:
(1) 对于 x = q[l + r >> 1], j 始终走到q[R - 1] 的位置, 因此为了不陷入死循环必须选择
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
因为选择 i 的话, i 即可能出现在 L 的位置上也可能出现在 R 的位置上, 当出现在第一种情况的时候(图中的情况一)不会有影响, 但是出现在情况二的时候就会出现陷入死循环的情况
quick_sort(q, l, i- 1), quick_sort(q, i, r);
以上代码代入就会出现quick_sort(q, l, l) , quick_sort(q, l, r), 对于第二个函数, 与我起初调用的函数想同, 这说明有一次执行了该函数, 因此下一次也会执行, 这样往复, 就陷入了死循环.
⚠ : 重点👑🌈🎉👉✨⭐
1. 分治点的选择
2. i++ 和 j--
3. 递归的参数的确定
还有另外一个版本的代码:
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>> 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, i - 1), quick_sort(q, i, r); }
二. 归并排序
(也是分治的思想）✅
1. 将数组从中间分开, 分别对其按照这三步进行排序, 直到无法分割
2. 把两边排好序的数组再次进行统一排序
3. 再将左右两个数组进行合并
👑 思路 : 先细后整, 先保证这部分是排好序的, 直接那这一部分去和另一部分排好序的进行组合, 这样整个数组就是排好序的
void merge_sort(int a[], int l, int r) { if (l >= r)return; int mid = l + r >> 1; merge_sort(a, l, mid); merge_sort(a, mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (a[i] >= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; while (i <= mid) temp[k++] = a[i++]; while (j <= r) temp[k++] = a[j++]; for (i = l, j = 0; i <= r; ++i, ++j) a[i] = temp[j]; }
🌈图解 :
三. 二分
✨整数二分：
看 mid(你选取的中点) 是 左边 还是 右边
代码 :
int bSearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; // 如果左边界满足就执行这个 else l = mid + 1; } return l; } int bSearch_2(int a[], int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; // 如果右边界满足就执行这个 else r = mid - 1; } return l; }
⭐总结的口诀 : 不管快排和二分, 中点偏左选右边, 中点偏右选左边
偏左 : mid = l + r >> 1
偏右 : mid = l + r + 1 >> 1
解释 : 中点分别对应快排中的分治点和二分中的中点, 当快排中的中点偏左那么就选 j (j 是右边的, i 是左边的), 反之, 选 i 为递归参数; 当二分中的中点偏左时, 那么就选r = mid, 反之选 l = mid.
✨浮点数的二分
浮点数二分主要变化为截至条件为 : ( r - l ) > 1e6 (差的值)
以下为求 n 的平方根的习题, 可以更好地理解浮点数二分
#include<iostream> #include<algorithm> #include<cstring> using namespace std; int main() { double n; cin >> n; double l = 0, r = n; while((r-l) > 1e-6) { double mid = (l + r)/2; if(n <= mid * mid) r = mid; else l = mid; } printf("%0.2lf\n", l); return 0; }
四. 前缀和
前缀和 : 顾名思义是数组中某元素前面的所有和或者部分和
为什么会出现它 : 求一段和的时间复杂度为 O(1)
✨ 一维前缀
a[1],a[2],a[3].....a[n]
s[i] = a[i] + a[i-1]...a[2] + a[1]
a[3] + a[4]...a[14] + a[15] = s[15] - s[3-1]
s[l,r] = s[r] - s[l-1]
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); //读入n个数
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; //处理前缀和
✨二维前缀
s[i][j] 表示二维数组中，左上角(1, 1)到右下角(i, j)所包围的矩阵元素的和
s[i][j] = s[i - 1][j] + s[i][j - 1 ] + a[i] [j] - s[i - 1][j - 1]
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]
五. 差分
差分就是将前缀和的操作反过来
已知 : s[i] 得到 a[i] = s[i] - s[i - 1]
差分的好处在于, 给一段数组加一个数只需要对两个位置( b[i] 和 b[j+1] )进行操作即可
🎉差分数组：
首先给定一个原数组a：a[1], a[2], a[3],,,,,, a[n];
然后我们构造一个数组b ： b[1], b[2], b[3],,,,,, b[i];
使得 a[i] = b[1] + b[2] + b[3] + ,,,,,, + b[i]
也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。
👉构造差分数组的时候的巧妙方法 : 初始化就进行差分
如下：(⚠ : b 数组从下标 1 开始)
a[0 ]= 0; (为了呈现规律, 可有可无)
b[1] = a[1] - a[0];
b[2] = a[2] - a[1];
b[3] = a [3] - a[2];
........
b[n] = a[n] - a[n - 1];
我们只要有b数组，通过前缀和运算，就可以在O(n) 的时间内得到 a 数组 。
✨差分的用处解析 :
给定区间[l, r ]，让我们把a数组中的[l, r] 区间中的每一个数都加上c,即 a[l] + c , a[l + 1] + c , a[l + 2] + c ,,,,,, a[r] + c;
始终要记得，a数组是b数组的前缀和数组，比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。
首先让差分b数组中的 b[l] + c ,通过前缀和运算，a数组变成 a[l] + c ,a[l + 1] + c,,,,,, a[n] + c;
然后我们打个补丁，b[r + 1] - c, 通过前缀和运算，a数组变成 a[r + 1] - c,a[r + 2] - c,,,,,,,a[n] - c;
