算法与数据结构

第1周

线性查找法

开课第一周，我们将学习最简单的算法：线性查找法。在学习这样一个最简单的算法的过程中，我们也将接触诸多概念：循环不变量，复杂度分析，如何使用泛型让我们的算法更通用，以及简单的性能测试方式。

第2周

排序基础

在这一周，我们将接触两个最基础的排序算法：选择排序法和插入排序法。虽然这两个排序算法很简单，但在这一周，我们将巩固我们之前学习的知识，将循环不变量的思路和复杂度分析应用在这些算法中。

第3周

数据结构基础：动态数组，栈和队列

这一周，我们开始接触最基础的数据结构：线性数据结构。这些数据结构看似简单，但是通过对他们的学习，会接触很多新的概念，包括对静态数组的扩容和缩容；均摊复杂度分析；数据结构的接口设计；循环队列，等等。

第4周

动态数据结构基础：链表

在这一周，我们将接触最基础的动态数据结构：链表。在学习链表的过程中，我们将更深入透彻地理解程序设计中“引用”的概念，更会开始接触程序设计中最常用的一种逻辑搭建方式：递归

第5周

归并排序法

我们将学习第一个高级排序算法：归并排序法。将看到更通用的递归算法的设计方法，理解自顶向下和自底向上，理解分治。看到归并排序法的优化，接触 O(nlogn) 这一复杂度的分析方式，归并排序思想的实际应用

第6周

快速排序法

本周，我们将学习第二个高级排序算法：快速排序法。将逐渐优化，完成四个版本的快速排序算法，并看到算法对不同数据表现出的差异。同时，也会简单介绍面对随机算法，我们的复杂度分析有何不同

第7周

二分查找法

我们将学一个看似基础但“变化多端”的算法：二分搜索法 我们将探索基础二分搜索算法的递归和非递归写法理解循环不变量和如何处理边界问题等等，很多算法面试甚至竞赛问题，本质都是二分搜索问题

第8周

二分搜索树

我们学习第一个基础树结构：二分搜索树。在学习二分搜索树的过程中，我们将大量使用递归，深入理解递归。同时我们会学习经典的数据遍历方式：DFS 和 BFS。还会接触两个最为常见的抽象数据类型：集合和映射

第9周

堆，优先队列和堆排序

我们将学习一个特殊的树结构：堆。学习后我们将看到数组也可以表示树结构。同时我们还会引出另外一种高级排序算法：堆排序。最后，我们将使用堆组建一种应用极其广泛的重要数据结构：优先队列，并拓展对队列的认识

第10周

冒泡排序，希尔排序和排序算法大总结

我们将再学习两个排序算法：冒泡排序和希尔排序法。其中希尔排序法是一种重要的排序方法，插入排序法的优势如何被应用乃至改造成一个全新的高效算法。同时进行一个大总结更加系统地梳理和排序算法相关的系列概念。

第11周

线段树，Trie 和并查集

我们将学习三种应用在不同场合的树结构：线段树，Trie 和并查集。学习后将看到不同的数据结构拥有解决不同问题的能力，了解如何根据问题不同的问题，选择合适的数据结构。

第12周

AVL 树和红黑树

我们将学习两种高级的二分搜索树结构：AVL 树和红黑树。理解二分搜索树的局限性，接触平衡树的概念。我们还会学习一种树结构：2-3 树，看到 2-3 树和红黑树的等价性也是后续我们学习 B 类树的基础

第13周

哈希表和 SQRT 分解

我们将首先学习哈希表这种重要的数据结构深入理解哈希的概念，并使用链地址法设计出属于我们自己的哈希表结构。同时将学习到分块这一概念并接触另外一个经典的使用分块的思想解决区间问题的数据结构：SQRT 分解

第14周

非比较排序

在这一周，我们将看到：排序算法不一定基于比较，不进行元素的比较也可以对某类特殊的对象进行排序，即非比较排序算法。我们将学习计数排序法，桶排序法和基数排序法。

第15周

模式匹配

我们将学习一类重要的算法：模式匹配。从基本的模式匹配出发，引出大名鼎鼎的 KMP 算法。对于 KMP 算法，我们会学习两种实现方式，并接触到计算机领域的一个重要的概念：状态机。

第16周

随机算法，外存算法和更多

最后一周，我们将看到更广阔的算法和数据结构的世界。将探索随机算法的世界，学习 Knuth 洗牌算法和蓄水池抽样算法。探索外存算法和数据结构的世界，学习 B 类树等，以及更多在外存中处理问题的方式和思想