1. 基础算法

1.1 排序

1.1.1 快速排序(不稳定)

• 快速排序是基于分治的思想

• 快速排序步骤
设有一个无序数组为q[n]n为数组大小
• 确定分界点x：q[l] ,q[r] ,q[(l+r)/2],随机选择
• 🌟调整区间：让所有小于等于x的数在x的左半边，所有大于等于x的数在x的右半边
• 递归处理左右两段

• 调整区间的方法
• 方法1(暴力):
• 新开两个数组a[]b[]
• 扫描数组q[n]：q[i] ≤ x，则将q[i]存入a数组；q[i] ≥ x，则将q[i]存入b数组
• 最后将两个数组a[]b[]合并到q[]
• 方法2(双指针挖坑法)：
• 给定原始数列如下，要求从小到大排序：
• 首先，我们选定基准元素pivot，并记住这个位置index，这个位置相当于一个“坑”。并且设置两个指针left和right，指向数列的最左和最右两个元素：
• 接下来，从right指针开始，把指针所指向的元素和基准元素做比较。如果比pivot大，则right指针向左移动；如果比pivot小，则把right所指向的元素填入坑中。
• 在当前数列中，1 < 4，所以把 1 填入基准元素所在位置，也就是坑的位置。这时候，元素 1 本来所在的位置成为了新的坑。同时，left向右移动一位。
• 此时，left左边绿色的区域代表着小于基准元素的区域。
• 接下来，我们切换到left指针进行比较。如果left指向的元素小于pivot，则left指针向右移动；如果元素大于pivot，则把left指向的元素填入坑中。
• 在当前数列中，7 > 4，所以把 7 填入index的位置。这时候元素 7 本来的位置成为了新的坑。同时，right向左移动一位。
• 此时，right右边橙色的区域代表着大于基准元素的区域。
• 下面按照刚才的思路继续排序：
• 8 > 4，元素位置不变，right左移
• 2 < 4，用2来填坑，left右移，切换到left。
• 6 > 4，用6来填坑，right左移，切换到right。
• 3 < 4，用3来填坑，left右移，切换到left。
• 5 > 4，用5来填坑，right右移。这时候left和right重合在了同一位置。
• 这时候，把之前的pivot元素，也就是 4 放到index的位置。此时数列左边的元素都小于 4，数列右边的元素都大于 4，这一轮交换终告结束。

• 快速排序模版

1.1.2 归并排序(稳定)

• 归并排序是基于分治的思想

• 归并排序步骤
设有一个无序数组为q[n]n为数组大小
• 确定分界点x：mid = (l+r)/2
• 递归排序left和right
• 归并(合二为一)

• 双指针算法

• 归并排序模版

1.2 二分查找算法

1.2.1 整数二分

• 整数二分的步骤
• case 1:
• 找到中间值：mid = (l + r + 1) / 2
• 判断并更新：
• case 2:
• 找到中间值并判断：mid = (l + r) / 2
• 判断并更新：

• 整数二分模版

1.2.2 浮点数二分

• 浮点数二分的步骤
• 找到中间值并判断：mid = (l + r) / 2
• 判断并更新：
• 满足则找到

• 浮点数二分模版

1.3 高精度(C++专属)

• 大整数存储方法：利用数组将每一位都存入数组，从头至尾为个位、十位、百位等等

1.3.1 高精度加法

• 高精度加法模版

1.3.2 高精度减法

• 高精度减法模版

1.3.3 高精度乘法

• 高精度乘法模版

1.3.4 高精度除法

• 高精度除法模版

1.4 前缀和与差分

1.4.1 一维前缀和

• 求和方法：利用递推s[i] = s[i - 1] + a[i]，此处规定s[0] = 0

• 作用：快速求出原数组一段的和，比如求区间a[i]的和为s[r] - s[l - 1]

• 前缀和模版

1.4.2 二维前缀和

• 计算矩阵的前缀和： s[x][y] = s[x - 1][y] + s[x][y - 1] - s[x - 1][y - 1] + a[x][y]

• 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为： s = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

• 二维前缀和模版

1.4.3 一阶差分

• 差分是前缀和的逆运算，对于一个数组a，其差分数组b的每一项都是a[i]和前一项a[i − 1]的差

• 作用：如果想要给a数组从[l,r]的所有数都加上c那么直接操作差分数组：B[l] += c, B[r + 1] -= c

• 一阶差分模版

1.4.4 二维差分数组

• 给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：

• 二维差分模版