精品课程 [大课程] — 算法与数据结构体系课【更新至第十三周】
慕课网算法名师Liuyubobobo，5年集大成之作
满足你从开始学编程到工作5年内的几乎所有算法学习需求
阶段一：算法与数据结构基础
第1周 线性查找法
开课第一周，我们将学习最简单的算法：线性查找法。在学习这样一个最简单的算法的过程中，我们也将接触诸多概念：循环不变量，复杂度分析，如何使用泛型让我们的算法更通用，以及简单的性能测试方式。
课程安排：
- 1、什么是算法
2、为什么要学习算法和数据结构
3、线性查找算法
4、使用泛型让算法更通用
5、自定义类测试算法
6、循环不变量
7、复杂度分析
8、常见算法复杂度举例
第2周 排序基础
在这一周，我们将接触两个最基础的排序算法：选择排序法和插入排序法。虽然这两个排序算法很简单，但在这一周，我们将巩固我们之前学习的知识，将循环不变量的思路和复杂度分析应用在这些算法中。
课程安排：
- 1、选择排序法
2、原地排序
3、使用泛型约束
4、Comparable 接口的使用
5、插入排序法
6、插入排序法的优化
7、排序算法的测试数据生成
8、排序算法的性能测试和比较
第3周 数据结构基础：动态数组，栈和队列
这一周，我们开始接触最基础的数据结构：线性数据结构。这些数据结构看似简单，但是通过对他们的学习，会接触很多新的概念，包括对静态数组的扩容和缩容；均摊复杂度分析；数据结构的接口设计；循环队列，等等。
课程安排：
- 1、理解静态数组和动态数组
2、如何封装属于自己的数据结构
3、动态数组的扩容和缩容
4、均摊复杂度分析
5、数据结构的接口设计
6、栈和栈的应用
7、队列和队列的应用
8、队列的优化：循环队列
9、双端队列
10、Java 语言中的设计问题讨论
第4周 动态数据结构基础：链表
在这一周，我们将接触最基础的动态数据结构：链表。在学习链表的过程中，我们将更深入透彻地理解程序设计中“引用”的概念，更会开始接触程序设计中最常用的一种逻辑搭建方式：递归
课程安排：
- 1、什么是链表
2、链表的更删改查
3、抽象数据接口
4、使用链表实现栈和队列
5、链表的性能问题
6、链表天然的递归结构
7、通过链表深入理解递归
8、经典链表相关的面试问题
阶段二：递归无处不在
第5周 归并排序法
我们将学习第一个高级排序算法：归并排序法。将看到更通用的递归算法的设计方法，理解自顶向下和自底向上，理解分治。看到归并排序法的优化，接触 O(nlogn) 这一复杂度的分析方式，归并排序思想的实际应用
课程安排：
- 1、归并排序的算法思想
2、归并过程
3、复杂的递归算法运行机制解读
4、归并排序法的复杂度分析
5、归并排序法的优化
6、自顶向下和自底向上
7、使用归并排序法求逆序数对
第6周 快速排序法
本周，我们将学习第二个高级排序算法：快速排序法。将逐渐优化，完成四个版本的快速排序算法，并看到算法对不同数据表现出的差异。同时，也会简单介绍面对随机算法，我们的复杂度分析有何不同
课程安排：
- 1、快速排序算法的基本思想
2、随机化的快速排序算法
3、二路快排
4、三路快排
5、不同快速排序算法的性能比较
6、快排的复杂度分析
7、快排思想的实际应用
第7周 二分查找法
我们将学一个看似基础但“变化多端”的算法：二分搜索法 我们将探索基础二分搜索算法的递归和非递归写法理解循环不变量和如何处理边界问题等等，很多算法面试甚至竞赛问题，本质都是二分搜索问题
课程安排：
- 1.二分搜索法的基本思想
2.二分搜索的递归实现
3.二分搜索的非递归实现
4.深刻理解程序设计中的边界问题
5.二分搜索在浮点数据中的应用
6.使用二分搜索解决寻界问题
7.避免死循环
8.二分搜索的模板
9.使用二分搜索法的思路解决实际问题
第8周 二分搜索树
我们学习第一个基础树结构：二分搜索树。在学习二分搜索树的过程中，我们将大量使用递归，深入理解递归。同时我们会学习经典的数据遍历方式：DFS 和 BFS。还会接触两个最为常见的抽象数据类型：集合和映射
课程安排：
- 1.什么是树结构
2.在数据结构中使用递归
3.深度优先遍历
4.广度优先遍历
5.Hubbard Deletion
6.抽象数据结构：集合
7.抽象数据结构：映射
8.集合和映射的经典应用
阶段三：算法与数据结构进阶
第9周 堆，优先队列和堆排序
我们将学习一个特殊的树结构：堆。学习后我们将看到数组也可以表示树结构。同时我们还会引出另外一种高级排序算法：堆排序。最后，我们将使用堆组建一种应用极其广泛的重要数据结构：优先队列，并拓展对队列的认识
课程安排：
- 1、数组也可以表示树结构
2、堆的基本操作
3、Sift Up 和 Sift Down
4、Heapify
5、堆排序
6、优先队列
7、优先队列的应用
8、广义队列
第10周 冒泡排序，希尔排序和排序算法大总结
我们将再学习两个排序算法：冒泡排序和希尔排序法。其中希尔排序法是一种重要的排序方法，插入排序法的优势如何被应用乃至改造成一个全新的高效算法。同时进行一个大总结更加系统地梳理和排序算法相关的系列概念。
课程安排：
- 1、冒泡排序的基本思想
2、冒泡排序的优化
3、希尔排序的基本思想
4、希尔排序的优化
5、什么是增量序列
6、基于比较的排序算法总结
7、稳定排序
第11周 线段树，Trie 和并查集
我们将学习三种应用在不同场合的树结构：线段树，Trie 和并查集。学习后将看到不同的数据结构拥有解决不同问题的能力，了解如何根据问题不同的问题，选择合适的数据结构。
课程安排：
- 1、线段树的基本操作
2、区间查询问题
3、Trie 树的基本操作
4、使用 Trie 解决模式匹配问题
5、并查集的基本原理
6、不断优化六个版本的并查集
7、并查集的应用
第12周 AVL 树和红黑树
我们将学习两种高级的二分搜索树结构：AVL 树和红黑树。理解二分搜索树的局限性，接触平衡树的概念。我们还会学习一种树结构：2-3 树，看到 2-3 树和红黑树的等价性也是后续我们学习 B 类树的基础
课程安排：
- 1、什么是平衡树
2、左旋转和右旋转
3、AVL 树
4、2-3 树
5、2-3 树和红黑树的等价性
6、红黑树保持平衡的基本操作
7、红黑树的添加操作实现
8、二分搜索树，AVL 树和红黑树的性能对比
9、词频统计应用
10、使用真实数据测试不同底层封装的集合和映射结构
第13周 哈希表和 SQRT 分解
我们将首先学习哈希表这种重要的数据结构深入理解哈希的概念，并使用链地址法设计出属于我们自己的哈希表结构。同时将学习到分块这一概念并接触另外一个经典的使用分块的思想解决区间问题的数据结构：SQRT 分解
课程安排：
- 1、哈希的基本思想
2、哈希函数的设计
3、链地址法
4、Java 中的哈希表
5、分块思想
6、SQRT 分解
7、使用 SQRT 分解处理区间问题
阶段四：更广阔的算法和数据结构世界
第14周 非比较排序
在这一周，我们将看到：排序算法不一定基于比较，不进行元素的比较也可以对某类特殊的对象进行排序，即非比较排序算法。我们将学习计数排序法，桶排序法和基数排序法。
课程安排：
- 1、非比较排序
2、计数排序法
3、桶排序法
4、基数排序法
5、LSD 和 MSD
6、非比较排序的性能测试
7、非比较排序和比较排序的性能对比
第15周 模式匹配
我们将学习一类重要的算法：模式匹配。从基本的模式匹配出发，引出大名鼎鼎的 KMP 算法。对于 KMP 算法，我们会学习两种实现方式，并接触到计算机领域的一个重要的概念：状态机。
课程安排：
- 1.朴素模式匹配算法
2.KMP 算法
3.KMP 算法中的 LPS 数组
4.状态机
5.状态机的其他应用
6.滚动哈希
7.RK 算法
8.RK 算法的经典问题
第16周 随机算法，外存算法和更多
最后一周，我们将看到更广阔的算法和数据结构的世界。将探索随机算法的世界，学习 Knuth 洗牌算法和蓄水池抽样算法。探索外存算法和数据结构的世界，学习 B 类树等，以及更多在外存中处理问题的方式和思想
课程安排：
- 1.随机算法
2.Knuth 洗牌算法
3.Knuth 洗牌算法的应用
4.蓄水池抽样算法
5.B 类树
6.外排序
7.更多外存算法和数据结构
8.大规模数据处理方式
9.更广阔的算法和数据结构
