算法与编程

1. 排序

1. 插入排序 - 遍历数组 O(n) * (查找在小于当前循环变量的序列中的位置 O(n) + 从目标位置开始的每个数都向后移动一位 O(n)) = O(n^2)

   1. 移动的实现逻辑：从后往前开始查找插入位置。移动时向后覆盖一位(第一次覆盖为当前循环变量的位置)

2. 折半插入排序 - 遍历数组 O(n) * (查找在小于当前循环变量的序列中的位置(使用二分查找) O(log(n)) + 从目标位置开始的每个数都向后移动一位 O(n)) = O(n^2)

3. 希尔排序 - 将数组拆分成 n 到 1 组的序列，一共 m (m<n) 轮次，每次对每一个拆分的序列做插入排序，最后一轮对整个序列做插入排序。时间复杂度是O(n^1.3) - O(n^2)

4. 冒泡排序 - O(n^2)

5. 快速排序 - 选择一个 pivot ，设置两个指针从数组分别在数组最左侧和最右侧，用两者分别从左往右和从右往左遍历数组，如果找到不符合顺序的（比如左指针指向的数大于pivot，右指针指向的数小于pivot）则将两者交换，知道左指针的值 >= 右指针的值，循环结束。循环结束的位置就是pivot在最终排序后的数组中的位置，需要额外做一次交换把pivot放到对应位置。这个操作的时间复杂度为 O(n) (遍历数组)。然后依次对 [0, pivot - 1] , [pivot + 1， 数组长度] 做快速排序。这个过程需要重复 log n 次。所以快速排序的时间复杂度为 O(nlogn)

6. 选择排序 O(n^2)

7. 堆排序 - 先根据需求的排序顺序构建大根堆或者小根堆 (大根堆 - A[i] >= A[2i] && A[i] >= A[2i+1]，小根堆反之)。构建大/小根堆的方法为，从非叶子节点开始向前循环，每次比较当前循环变量A[i], 与 A[2i], A[2i+1], (当然需要保证不越界)。如果当前的节点小于其中任意一个节点，则将A[i] 与 Max(A[2i], A[2i+1]) 互换。然后针对被互换的节点循环检测是否符合大/小根堆。当非叶子节点循环完根节点后，当前堆既为大/小根堆。这之后每次把数组最顶端的元素和最后一个元素互换，并让循环终止条件向前移一个元素 (忽视最后一个元素)，之后使不包含最后一个元素的数组重新成为大根堆/小根堆，直到数组中没有元素。除了第一次构建以外，总共循环数组长 n 次，每次构建大根堆/小根堆的复杂度为 O(log n)，因为实际上只移动一个节点 (也就是被互换的节点)，节点最多移动为树的深度 log n。所以堆排序的复杂度为O(nlogn)。

8. 归并排序 - 先把数组拆分成log n个 2元组 (实际上是拆分到单个元素，然后除法边界条件开始merge)，每个内部排序，然后两两合并。合并时设置两个指针分别指向两个数组的元素，按需求的顺序对比两个指针指向的元素然后放入目标数组。所以最多需要O(n)次比较操作，而一共合并需要log n次，所以总算法复杂度是O(nlogn). 这个方法需要一个辅助数组B (在合并时防止A中数据被覆盖), 其长度等同于A。所以空间复杂度为O(n)

9. 基数排序 - 需要先知道数组中所有值的最大位数，以及数组中单个位的基数（radix）,也就是每一位的所有可能情况以及顺序。然后根据Most Significant bit 或者 Least Significant bit进行 每一位的排序。如，第一步将所有数字按个位放入 a[0] - a[9]的数组中，然后按数组中的顺序存回原数组。第二步按十位，第三步按百位，以此类推。空间复杂度是 O(n), 时间复杂度是 O( (n + 基数) * 数据最大位数)。实现该空间复杂度的前提是在额外数组中的读写操作都是O(1), 也就是说使用二维数组实现时需要对每个情况维护一个尾指针。

2. 树与二叉树

1. 树和二叉树

2. 前序遍历，中序遍历，后序遍历，层序遍历

3. 二叉线索树 - 在普通的树节点上增加 Ltag, Rtag两个标志，表明该节点的左右指针指向的是左右孩子，还是对应顺序中的前后继。

   1. 线索化 - 在进行对应顺序的遍历时，先添加 全局变量 Pre在，初始化为null，表示第一个访问的节点的先继为Null。然后在visit(TreeNode)函数中加入以下步骤
      1. 检测当前访问节点（指针）的左孩子是否为NULL，如果是，则将Ltag = 1, Lchild = pre
      2. Pre 指向的节点如果不为null ，且该节点的右孩子地址为Null，设置Pre指向节点的 Rtag = 1，Rchild = 当前访问的节点。
      3. 退出遍历时，将Pre = 最后一个节点，Pre指向的节点的右孩子设置为Null
   2. 中序线索二叉树 - 适用1所说的线索化
   3. 先序线索二叉树 - 适用1所说的线索化。因为访问顺序是根左右，所以会出现没有左子树的节点的先继是他的父节点的情况。如果这是直接调用递归的遍历访问他的左子树会出现循环调用的问题。所以在递归实现的先序遍历中，添加仅在Ltag == 0的情况下才访问当前节点的左子树。
   4. 后序线索二叉树。适用于1所说的线索化。
   5. 通过线索二叉树找节点的前驱和后继
      1. 中序线索树找后继 - 要么1. 节点记录有后继，直接输出；2. 节点有右子树，访问右子树最左下的节点 (中序遍历 - 左根右 中的第一个节点)。全树的第一个节点同理，是根的最左下的节点。
      2. 中序线索树找前驱 - 要么1. 节点记录有前驱，直接输出；2. 节点有左子树，访问左子树最 右下的节点 (中序遍历 - 左根右 中的最后一个节点)。全树的最后一个节点同理，是根的最右下的节点。
      3. 先序线索树找后继 - 情况1相同。情况2在有左右两个孩子的情况下，考虑先序遍历的顺序 - 根左右。所以当前节点的后继一定是左孩子（左右孩子都存在的情况），或者右孩子（只有右孩子的情况）
      4. 先序线索树找前驱 - 无法实现，因为需要访问当前节点的父节点，而线索树无法通过O（1）找到父节点，只能从头遍历。如果线索树记录了指向父节点的指针，那么分3种情况讨论。1. 当前节点是父节点的左孩子。2. 当前节点是父节点的右孩子，且父节点没有左孩子。3. 当前节点是父节点的右孩子，且父节点有左孩子。同样考虑先序遍历的顺序即可。
      5. 后序线索树找前驱 - 左右根，讨论根节点是否有右孩子。
      6. 后序线索树找后继 - 无法实现，参考4

4. Huffman Code - 出现次数越多的编码，在树中的深度越浅。

   1. Huffman Tree - 叶节点的带权路径和值最小的二叉树（最优二叉树），不唯一。
   2. 构造方法 - 每次从所有的叶子节点中选择权重最小的两个节点，把他们合成一棵树。这棵树的根节点的权重为两个叶子节点的权重的和。然后在原来的叶节点集合中移除被合并的两个叶节点，并加入他们的根节点。重复此过程直到所有的节点全部被合并。
   3. Prefix code - 没有任意一个编码是其他编码的前缀
   4. 可变长编码 - 允许对不同字符用不同长度的二进制表示。

3. 查找

1. 二分查找

2. 二叉搜索(排序)树 - 左子树 < 根 < 右子树

   1. 查找 / 插入 - Key == root return root; Key < root , insert / search (root. leftchild) ; Key > root, insert / search(root. rightchild).
   2. 删除
      1. 如果是叶节点，直接删除
      2. 如果只有左子树 / 右子树，让子树的根节点成为新的根节点
      3. 如果左右子树都有，则将当前节点替换为他的直接前继 / 直接后继，（左子树的最右下节点 / 右子树的最左下节点，参考二叉搜索树）然后删除他的直接前继 / 直接后继。
   3. 效率 - 取决于树的构造。是O(logn)的正比。

3. 平衡二叉树/AVL tree - 任意节点的左子树和右子树高度差不超过1

4. Hash表 - 将关键字值通过Hash function ( H(key) ) 映射到一个新的数组下标。需要考虑同一个键值引起的冲突。冲突解决方法有一下几种：

   1. 链接法 / Chaining - 将冲突的元素形成链表，使Hash表中对应的索引值指向这个链表
   2. 开放定址法 / Open Addressing - 通过某种方式找到哈希表中的下一个空位，将冲突的元素填入第一个相同元素对应的索引值的下一个空位
      使用Open Addressing的哈希表在删除元素时需要注意不能直接删除元素，因为如果直接删除，则会影响冲突元素的查找。取而代之的是先设置为"Deleted"或者别的标签。然后定期重建表。

5. 队列