学习算法思想

发表于 | 分类于

学习算法思想

第一章：当我们在讨论算法的时候，我们在讨论什么？

  1. 我们究竟为什么要学习算法

  2. 课程介绍

第二章：排序基础

​ 2-1 选择排序法
​ 2-2 使用模板（泛型）编写算法
​ 2-3 随机生成算法测试用例
​ 2-4 测试算法的性能
​ 2-5 插入排序法
​ 2-6 插入排序法的改进
​ 2-7 更多关于O（n*2）排序算法的思考

  1. 冒泡排序（n²）：
  2. 选择排序（n²）： 在[i..n)未排序的数组里获取最小的值放在已排序数组的后面，即放在i的位置。
    缺点：两层循环必须都执行完，所以效率低。
  3. 插入排序（n²）：在未排序数组中取第一个数，跟已排序的数组元素比较，插入到合适的位置。
    优点：在数组近乎有序的情况下，可以O(n)的时间复杂度。设置比O(nlogn)效率还要高。

第三章：高级排序问题

​ 3-1 归并排序法
​ 3-2 归并排序法的实现
​ 3-3 归并排序法的优化
​ 3-4 自底向上的归并排序算法
​ 3-5 快速排序法
​ 3-6 随机化快速排序法
​ 3-7 双路快速排序法
​ 3-8 三路快速排序法
​ 3-9 归并排序和快速排序的衍生问题

第四章：堆和堆排序

​ 4-1 为什么使用堆
​ 4-2 堆的基本存储
​ 4-3 Shift Up
​ 4-4 Shift Down
​ 4-5 基础堆排序和Heapify
​ 4-6 优化的堆排序
​ 4-7 排序算法总结
​ 4-8 索引堆
​ 4-9 索引堆的优化
​ 4-10 和堆相关的其他问题

  1. 二叉树（Binary Tree）： 二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

  2. 二叉查找树（Binary Search Tree）： 二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。它是怎么做到这些的呢？这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

  3. 满二叉树： 二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。

  4. 完全二叉树： 二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。

  5. 二叉堆： 堆是一个完全二叉树；堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

    实现一个堆：

    • 将n个元素逐个插入到一个空堆中，时间复杂度 是O(nlogn)。需要开辟额外的空间，空间复杂度是O(n)。

    • 从2/n的位置开始heapify的过程，算法复杂度为O(n)。在原数组实现为堆，空间复杂度是O(1)。

    堆的使用：用于排序，求第K大的元素等。

    • 大顶堆
    • 小顶堆

    堆排序的时间复杂度O(nlogn)

第五章：二分搜索树

​ 5-1 二分查找法
​ 5-2 二分搜索树基础
​ 5-3 二分搜索树的节点插入
​ 5-4 二分搜索书的查找
​ 5-5 二分搜索树的遍历（深度优先遍历）
​ 5-6 层序遍历（广度优先遍历）
​ 5-7 删除最大值，最小值
​ 5-8 二分搜索树的删除
​ 5-9 二分搜索树的顺序性
​ 5-10 二分搜索树的局限性
​ 5-11 树形问题和更多树。

  1. 二叉搜索树：二叉查找树（Binary Search Tree）二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。它是怎么做到这些的呢？这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
  2. 红黑树：平衡二叉树。

**（这一章往后还没有看）

第六章:并查集

​ 6-1 并查集基础
​ 6-2 Qucik Find
​ 6-3 Quick Union
​ 6-4 基于size的优化
​ 6-5 基于rank的优化
​ 6-6 路径压缩

第七章:

​ 7-1 图论基础
​ 7-2 图的表示
​ 7-3 相邻点迭代器
​ 7-4 图的算法框架
​ 7-5 深度优先遍历和联通分量
​ 7-6 寻路
​ 7-7 广度优先遍历和最短路径
​ 7-8 迷宫生成，ps抠图–更多无权图的应用

第八章：最小生成树

​ 8-1 有权图
​ 8-2 最小生成树问题和切分定理
​ 8-3 Prim算法的第一个实现
​ 8-4 Prim算法的优化
​ 8-5 优化后的Prim算法的实现
​ 8-6 Krusk算法
​ 8-7 最小生成树算法的思考

第九章：最短路径

​ 9-1 最短路径问题和松弛操作
​ 9-2 Dijkstra算法的思想
​ 9-3 实现Dijkstra算法
​ 9-4 负权边和Bellman-Ford算法
​ 9-5 实现Bellman-Ford算法
​ 9-6 更多和最短路径相关的思考

第十章：结束语

​ 10-1 总结，算法思想，大家加油！