算法基础

· 2021-11-29 · # 学习笔记

基础算法整理❗️

冒泡排序 $O(n^2)$

n次遍历每次从1到n判断相邻的数字是否左小右大否则swap
选择排序 $O(n^2)$

n次遍历每次找出最小数添加到一个新数组
插入排序 $O(n^2)$

n次遍历每次将当前数添加到一个新数组末尾，并从后向前依次swap直到遇到一个小于等于当前数的数字。
希尔排序 $O(n^2)$

n次遍历，每次将第i个数字与前面的数字swap知道遇到一个小于等于当前数的数字。
归并排序 $O(nlogn)$

每次将数组分成两段，分别处理好两段后合并起来。（递归）
快速排序 $O(nlogn)$

以中间数为基准数。双指针分别从前从后跑，遇到 $a_i$ 大于等于中间数 $a_j$ 小于等于中间数则swap。直至$ i>j $。则$ j $左边的数全部小于中间数，$ i$右边的数全部大于中间数。之后递归处理。
计数排序 $O(n)$

简易桶排序。每个数字放进对应的桶中++。遍历输出。
桶排序 $O(n)$

可以限定桶个数的升级桶排序。

二分查找
二分答案

日报：二分边界问题

关于二分的问题在这份日报中讲的十分清晰。

分为两种方法，一种为记录中间值，另一种不记录。

不记录的情况则需要根据 $l = mid$ 还是 $l = mid + 1$ 小心死循环的情况。

总之遇到二分题的时候，认真思考判断边界的处理即可。

（当然直接使用记录中间值的方法也是一种不错的选择）

如果二分答案的值是小数，采取二分多次的方法（如1k或1w）来达到精度要求即可.
01分数规划：

待补习。

前缀和:

线性 / 二(多)维 / 树上

还有基于dp的高维前缀和等等
差分:

维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。

即多次区间加减，离线查询。

差分数组： b[i] = a[i] - a[i - 1]。差分数组的前缀和就是原数组

树上差分：

分为点差分和边差分。待补习。

维护两个指针 $l,r$ ,每次确定区间的左端点,让 $r$ 不断向右移动,直到满足条件停下,维护一下答案,直到 $r>n$ 或者其它情况

离散化本质上可以看成是一种哈希，其保证数据在哈希以后仍然保持原来的全/偏序关系。

通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照从大到小编号来处理问题，即离散化。

用来离散化的可以是大整数、浮点数、字符串等等。

sort(lsh+1,lsh+1+n);

cnt = unique(lsh+1,lsh+1+cnt) - lsh - 1;

ID(x) = lower_bound(lsh+1,lsh+1+cnt,x) - lsh;

按左端点排序，贪心从左向右依次合并。