最近开始重拾算法的学习了，毕竟也要开始准备实习了，就用这个来记录一下我的算法的学习过程吧
1. 排序
排序算法常用的有两种：快速排序和归并排序，这两种算法都是基于分治的思想进行的。其他几种不是很重要，需要的时候再去了解即可，而且开发时也基本不需要自己写排序算法
快速排序
快速排序的过程：
在数组中随机选取一个基准值，一般来说会选择两边的数字或者中间的数字
遍历数组，将小于等于基准值的数放到基准值的左边，大于基准值的数放到基准值的右边
基准值将数组一分为二，递归处理左右两边即可
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
int nums[N];
// l和r为闭区间
void quick_sort(int l, int r) {
// 如果只剩区间内只剩一个数或者没有数则不用排序
if (l >= r) return;
// 左右端点需要分别进行扩展，防止边界情况
// 这里的x必须表示基准值，不可以换成下标，因为在遍历过程中下标会被改变，相应的基准值也会被改变
int x = nums[l + r >> 1], i = l - 1, j = r + 1;
while (i < j) {
do i ++; while (nums[i] < x);
do j --; while (nums[j] > x);
if (i < j) swap(nums[i], nums[j]);;
}
// 最后i >= j，所以j属于左半区间，i属于右半区间，所以是分别处理l到j和j + 1到r区间
quick_sort(l, j);
quick_sort(j + 1, r);
}归并排序
快速排序是先将数组分段，对大数组进行一个基本的划分之后再处理左右两个区间。而归并排序则恰好相反，先选中一个分界点，将分界点左右两侧的小数组先排序，再将排序结果合并。
归并排序的过程：
选择分界点，一般是两侧索引的平均值
对分界点左右两侧的区间进行排序，排完序之后左右两侧的数组都是有序的。
将两个排好序的数组合并，具体合并方式采用双指针分别指向两个数组
使用一个更大的数组存放归并结果，两个指针谁更大谁就放入大数组中。
代码实现
#include <iostream>
using namespace std;
int num[], temp[];
merge_sort(int l, int r) {
// 如果数组中只有一个数则直接返回
if (l >= r) return ;
int mid = l + r >> 1; // 找到分界点
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
// 通过双指针选择两个数中更小的哪个加入数组
while (i <= mid && j <= r) {
if (num[i] <= num[j]) temp[k++] = num[i++];
else temp[k++] = num[j++];
}
// 将剩下的数全部放入数组中
while (i <= mid) temp[k++] = num[i++];
while (j <= r) temp[k++] = num[j++];
// 将temp中的结果复制回到原数组中
for (i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];
}tips：需要注意的一点就是边界问题，边界的开闭性一定要一致，示例代码采用的是闭区间，如果是左开右闭需要在相应的位置增加或减少=号
2. 二分查找
二分查找是用来在有序数组查找满足条件的元素的一种非常高效的算法，二分查找不一定只能用于数字类型的数组，只要数组内的元素中的某个属性可以进行比较即可。其核心思想是利用数组的有序性来快速缩小查找范围，每次通过直接查找数组中间的元素来缩小一半的查找范围
代码实现
#include <iostream>
using namespace std;
bool check() {
// 检查元素是否满足条件的函数
}
// n是元素数量，即数组长度
int bi_search(int a[], int n) {
// 为了防止数组全部都是满足条件或不满足条件的极端情况，这里初始值设置从成了1和-1
int l = -1, r = n + 1;
while (l + 1 != r) {
int mid = l + r >> 1;
if (check(a[mid])) l = mid;
else r = mid;
}
// 这里根据需要返回，如果要求的是满足条件的则返回l对应的元素，如果寻找的是第一个不满足条件的元素则返回r对应的元素
return a[l];
}3. 前缀和与差分
前缀和
前缀和与差分与其说是算法，不如说是公式或者是思想。
假设有数组：a1, a2, a3, ..., an-1, an。
则其前缀和也为一个数组：s0, s1, s2, s3, ..., sn-1, sn。其中si = a1 + a2 + a3 + ... + ai-1 + ai，即si的值就是a数组中的前i个元素的和。其最常用的场景就是求数组的区间和。
前缀和相关公式： si = s~i - 1~ + ai（求si时使用），si - sj = aj+1 + aj+2 + aj+3 + ... + ai-1 + ai （求区间和时使用）。
为了同一表示区间和，我们规定s0 = 0，以便我们不需要对0进行特判，但是这样就要求数组下标必须从1开始。
因为只是公式，具体代码实现比较简单，这里就不在赘述。
差分
差分是前缀和的逆运算。
假设有假设有数组：a1, a2, a3, ..., an-1, an。
则构造一个新数组：b1, b2, b3, ..., bn-1, bn。使得bi = a1 + a2 + a3 + ... + ai-1 + ai。即a数组是b数组的前缀和，则b数组称为a数组的差分。求bi的方式也很简单，只需要另b1 = a1, b2 = a2 - a1, b3 = a3 - a1 ...。
显然我们可以通过差分数组来求原数组，只需要对差分数组求一遍前缀和就可以了，和前缀和一样，为了统一表示，我们令b0 = 0，所有下标统一从1到n表示。
for (int i = 1; i <= n;; i ++) a[i] = b[i] + b[i - 1];差分的一个常见应用场景是对原数组的某一个区间中的所有数进行加减一个常数的操作。假设现在我们需要对a数组中下标从l到r中的所有数全部加上一个常数c，而其他数字保持不变，那么我们通过差分数组便可以将原来O(n)时间复杂度的操作变成O(1)时间复杂度，具体实现代码如下：
void insert(int l, int r, int c) {
b[l] += c; // 让a[l]及以后的元素加上c
b[r + 1] -= c; // 让a[r]以后的元素减去c
}4.双指针
双指针也是和前缀和差分一样，是一种思想，在很多的题目和算法中都会用到，例如在快速排序中，就是利用双指针实现将数组分成两个区间的，在归并排序中合并排序结果时，就是使用两个指针分别指向两个数组。
双指针的主要作用就是将O(n2)时间复杂度的操作化简到O(n)时间复杂度，原来我们需要两重循环来枚举ij，现在i和j每个指针最多移动n次（每个指针只会向前移动而不会向后移动），时间复杂度相应地也就会降低到O(n)。在实际题目中，双指针主要会结合其他算法一起使用，建议遇到相关题目再进行训练。
双指针一般有三种使用形式：
快慢指针：一个fast指针，一个slow指针，fast指针的步长大于slow指针，典型使用场景是判断链表中是否有环。
对撞指针：两个指针最开始分别指向数组两端，不断向中间移动。
滑动窗口：一般是右端向右移动，达到停止条件停止右移，左端向右端逼近，左端逼近达到停止条件之后停止右移，然后右端继续右移。
5.lowbit运算
lowbit(x)返回的是x的二进制表示中最后一位1。例如x = 1010， 则lowbit(x) = 10。x = 10010000， lowbit(x) = 10000；
具体实现如下
int lowbit(int x) {
return x & (-x);
}原理：在计算机中数字都是以补码形式存储的，而正数的原码等于补码，负数补码＝反码 + 1，而一对相反数在原码上只差了一位符号位，数值位是相同的，负数在从原码向补码转换的过程中，转换方法是，从低位向高位的第一个1不变，而这个1左边的所有数值位全部取反。这样x & (-x)，由于第一个1左边高位的数值位全部取反了，所以&操作得0，又因为第一个1右边全部都是0（不论x还是-x），因此&操作全部为0，只会保留第一个1。
lowbit操作的一个常见使用场景是求一个数的二进制表示中1的个数，核心思想是lowbit计算结果后从x中减去这个结果，直到x减为0
int count1(int x) {
int count = 0;
while (x) {
x -= lowbit(x);
count ++;
}
return count;
}6.离散化
有时，我们可能会面临数据跨度很大，但是数量却很少的情况，简单来说就是数据零散稀疏，例如数的值域可能在-109 - 109之间，但是数据的数量可能很小，此时如果我们要存储每个数据在数组中出现的次数，那么开一个109大的数组肯定是不现实的，这便是离散化要解决的问题。离散化的核心思想是将零散稀疏的数据映射成连续，密集的数据，我们只关心数据的相对位置，而不关心其绝对大小。
例如现在有如下数据：1，1000000， 100000000， 20000， 30000。
则可以将这个数组映射到一个数组：[1，20000，30000，1000000，100000000]；我们通过数据的相对大小构建了一个新的数组，这个数组是连续的。
在实现离散化时，我们主要关心两个问题：
如何解决数组中的重复元素
如何确定一个数离散化后的位置
对于第一个问题，我们可以使用c++提供的库函数来实现
vector<int> all;
sort(all.begin(), all.end()); // 先对数组中的内容进行排序
/*
对排序后的数组去重，unique()函数会将给定区间内的元素去重，然后返回去重后的数组的尾地址，但是重复的元素会被放到这个数组的后面，这时可以使用vector的erase函数来将这段区间内的元素擦除，这样留下的便是去重后的数组
*/
all.erase(unique(all.begin(), all.end()), all.end());对于第二个问题，由于离散化后的数组是有序的，因此我们可以用二分查找便可以很快地定位到每个数组应该插入的位置
// 我们要找的是大于等于x的第一个位置
int find(int x) {
int l = -1, r = all.size();
while (l + 1 != r) {
int mid = l + r >> 1;
if (all[mid] < x) l = mid;
else r = mid;
}
// l是小于x的边界，因此大于等于x的第一个位置就是r
return r;
}离散化的一个典型适用场景是区间求和
7.gcd算法
gcd算法是用来求两个数的最大公约数的算法，原理是辗转相除法
int gcd(int a, int b) {
return b ? gcd(b, a%b) : a;
}8.区间合并
给定一系列区间，要求将有交集的区间合并成一个大区间。
区间合并的过程有点类似于贪心：
将所有区间按照左端点大小升序排序
从前两个区间开始依次合并，我们假设当前维护的区间的左右端点分别是st和ed，对于每次合并，有三种情况：
当前区间的左端点小于等于ed，且右端点也小于等于ed：st和ed不变，因为当前区间全部包含在在维护区间的内部
当前区间的左端点小于等于ed，右端点大于ed：将ed设为当前区间的有端点
当前区间的左端点大于ed：两个区间没有交集，则当前维护区间已经没有可以合并的区间了，将当前维护区间添加到答案集合中，当前遍历到的区间成为新的维护区间，st和ed更新为相应的左右端点
代码实现
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
vector<PII> segs; // 存放原始区间，这里假设已经输入完成
vector<PII> ans; // 存放合并后的区间
void merge() {
// 在c++中pair排序优先根据左端点排序，左端点相同再根据右端点排序，刚好可以满足我们的需求，因此这里不需要重写比较器
sort(segs.begin(), segs.end());
int st = segs[0].first, ed = segs[0].second;
for (int i = 1; i < segs.size(); i ++) {
int l = segs[i].first, r = segs[i].second;
if (l > ed) {
ans.push_back({st, ed});
st = l, ed = r;
}
else if (r > ed) ed = r;
}
// 循环结束之后要将最后一组放入
ans.push_back({st, ed});
}总结：这一章学习的主要是一个最基础最简单的算法，它们往往不会直接在题目中应用，而是结合其他高级算法一起使用，这些基础算法或思想在很多高级题目或算法中都会见到。