算法基础简单整理

[javanli]

1. 排序算法

   1. 选择排序

      • 每次选最小的放到最前面。一种naive的排序，没有实际用途。

   2. 插入排序

      • 每次将新的数据插在合适的位置。通过插入的方式在收到新数据时维护数据的顺序，相当于把排序的损耗分散到数据输入时。但单纯用来排序是意义不大的。

      • 希尔排序

        • 一种优化的插入排序。按一定步长将数组分成K组，在每组内进行插入排序；逐步缩小步长直至1。数据量比较小时性能比较好，但最坏时间复杂度仍是O(N^2)的。

   3. 归并排序

      • 递归地将数组分成两部分排好序再合并。时间复杂度O(NlogN)。稳定的。

   4. 快速排序

      • 取一个数，将比这个数小的放左边，大的放右边；重复这一过程。不稳定。平均复杂度为O(nlogn)，最坏为O(n^2)

   5. 堆排序

      • 堆是一种完全二叉树：每个结点的值都大于或等于其子节点的值，称为大顶堆。反之为小顶堆。
      • 将待排序序列构造为一个大顶堆，取走根节点；将剩余元素重新构造大顶堆；重复这一过程。
      • 复杂度O(nlogn)，不稳定

   6. 依赖数据范围的排序算法

      1. 计数排序

         1. 数组长度是数据范围，把所有数据放进去，自然排好序。复杂度O(n+k)，其中k是数组长度。

      2. 基数排序

         1. 对k位数，每一位进行排序。复杂度是O(k*n)，如果数据范围为N，十进制时k就是logN，大部分实际场景下N是int32或int64，这样导致实际复杂度大于O(nlogn)。

      3. 桶排序

         1. 每个桶对应一定的数据范围，把数据放到不同的桶里，然后对每个桶内进行排序。

2. 查找

   1. 二分查找：略
   2. 二叉树：略

   3. 二叉排序树（二叉查找树/二叉搜索树）

      1. 性质：左子树所有节点都小于根节点，右子树所有节点都大于根节点。
      2. 查找的平均复杂度是O(logn)的，这个跟一般的二分查找一样；但它插入复杂度也是O(logn)的，这就是优点了。
   4. 哈夫曼树/哈夫曼编码：参考https://blog.csdn.net/FX677588/article/details/70767446

   5. 平衡二叉树

      • 性质：左子树和右子树的深度之差不超过1
      • 目的：为了防止树极度不平衡的极端场景出现
      • 实现：AVL树、红黑树

   6. B树

      • 每个节点最多有m-1个关键字；每个节点的关键字从小到大排序，每个关键字的左子树中所有关键字都小于它，而右子树中的所有关键字都大于它。
      • 可以理解为二叉搜索树的推广形态。当m=2时，即二叉搜索树。
      • B+树：B树的推广，内部节点不保存数据，只用于索引，所有数据都保存在叶子节点。

   7. 字典树（Trie树）

      • 每个节点代表一个字符，有相同前缀的单词有公共的前缀节点。
      • 查询、插入复杂度都是O(L)，L是字符串长度
   8. 散列表：略

3. 字符串

   1. 字符串匹配KMP算法

      1. 类似状态机的方式，参考字符串匹配的KMP算法

   2. 最长公共子串 / 最长公共子序列

      1. 都是dp，参考动态规划：最长公共子串 & 最长公共子序列

4. 图

   • 待补充