生活中，排序操作无处不在，列队出操的时候，需要让同学们从矮到高依次站好，举行运动会的时候，会把每位运动员的成绩从高到低排序。在计算机的存储结构中，分为内存和外存，前者相对后者来说速度快、容量小，因此，当整个排序过程中所有的记录都可以直接放入内存中时，我们称之为内排序。可以按照什么策略来进行排序？每种排序算法的时间代价是多少？这一模块中，你将会学到三种类型的排序算法：插入排序、选择排序和交换排序，并了解到各个算法的稳定性和时间代价。重点：排序问题的基本概念，时间和空间复杂度分析（比较次数和移动次数，一个swap操作是3次移动）；直接插入排序、Shell排序、直接选择排序、堆排序、冒泡排序、快速排序的实现。难点：快速排序的实现及其优化、时间复杂度分析。PS：我们这门课程一直处在不断地建设与优化当中，吸取了很多以往课程的经典视频，所以如果你看到视频中出现了不同课程的名字，也不要惊讶哦，因为你正在集百家所长：）

有些算法时间代价太大？有的时候可以根据数据本身的特性，或是排序的特殊要求，调整排序的策略。例如，现在要将一叠试卷按得分从高到低排序，假设老师只给了“合格”、“不合格”两种分数，相信你立马就能整理好。原因就在于你并不需要再去整理所有“合格”试卷的相对次序了。本模块中，你将会学习到归并排序、分配排序和索引排序，并了解它们各自的基本思想、适用范围和时间代价。 重点：归并排序及其优化、桶式排序、静态/链式基数排序的实现、地址索引排序的结果整理。 难点：归并排序的实现、排序问题的下限的决策树分析方法（了解即可）。

当待处理的数据对象非常多，以至于内存容纳不下所有数据时，如果我们仍旧按照内排序的算法进行排序，大量的I/O会使得时间代价非常大，那应该怎么办呢？一般我们需要将数据文件分成若干段，每次将一段放入内存中进行排序，得到一系列的顺串，最后通过逐趟归并顺串，形成对整个数据文件的排序文件。在这一模块中，你将学到如何让初始文件形成尽可能长的初始顺串、如何通过增加每次参与归并的顺串个数，来减少对数据扫描的趟数，从而减少访问外存次数提高排序效率。 重点：置换选择算法、二路归并算法、赢者树算法的基本思想和实现。 难点：败者树的类定义及其成员函数的实现。

检索是一种常见的、也是必不可少的运算。在数据量很小的时候，顺序检索就可以快速找到目标，但当数据量很大的时候，顺序检索的效率就很差了。那如何在这种情况下进行检索呢？生活中，比如我们要查一个英文单词在字典的哪一页，我们可以根据拼写，判断这个单词是在当前页之前还是之后；又比如我们也可以问一个“天才”，他能直接告诉我们那个词在第几页。那如何找到、创造这样的“天才”呢？通过本模块的学习，除了检索的基本知识、基于线性表的检索方法、对集合的检索外，你还会学习到一种可以根据关键码值直接找到记录存储地址的方法——基于散列表的检索。 重点：检索最重要的度量是平均检索长度ASL。检索效率的分析需要注意成功检索和失败检索两种情况。散列函数的选择、冲突和聚集的解决方案（开散列、闭散列），散列方法的实现及其效率分析。 难点：负载因子、散列函数的选择、闭散列方法中的双散列。

索引相当于图书馆的卡片目录，有了卡片目录之后，就不需要在整个书库中搜索某一本书，而可以在卡片目录中检索到该书的位置。有了索引技术之后，我们可以高效地进行检索、插入、删除等操作。如何来实现索引？如何动态地调整索引？如何提高在索引中的检索效率？通过这一模块的学习，你会了解静态索引、倒排索引的相关知识，B树B+树是如何维护的，红黑树又是通过怎样的调整，提高增删和检索效率的。 重点：要充分理解索引的意义。也就是（key, pointer）。基于属性的倒排、对正文文件的倒排、B/B+树的概念及相关操作、红黑树的定义和数学性质、红黑树的插入/删除操作。 难点：注意多级索引的建立是动态的，在整个建索引的过程中都要保持结构，并且保持性能。B/B+树要注意阶（子结点数）和关键码数目的限制，另外要注意插入时候的分离，删除时候的借关键码、合并结点。B树的隐含指针（指向key本身在外部主文件中的地址）。红黑树插入算法首先是采用BST的方法把结点插入到位，然后注意调整，尤其是“红红”冲突的解决。

生活中，很多事物是有层次结构关系的，如果只是用线性表之类的简单数据结构来描述，就会丢失一些重要的信息。另一方面，为了支持动态数据结构，操作系统需要对内存进行动态地分配和回收，但也因此会产生如“碎片问题”、“内存泄露”等问题。如何利用高级数据结构来描述实际问题？如何实现相应的高级数据结构？如何管理内存分配，使内存利用率更高？通过本模块的学习，你将会了解多维数组、广义表这两个高级数据结构的实现，以及多种内存动态分配和回收的技术。 重点：特殊矩阵和稀疏矩阵的计算，了解索引下标的规律（例如，特殊矩阵多维到一维下标的相互映射）。广义表的存储结构可以看成是树和图结构的综合，理解和运用广义表的 head(), tail()两个函数。内存管理系统可以看成线性结构的应用。 难点：稀疏矩阵的十字链表存储有很多应用。广义表的结构和遍历，注意广义表的线性表顺序结构、树层次结构、图mark标记的结合

你是不是发现，二叉搜索树的运行效率并没有想象中那么好？这是因为二叉搜索树是一种基于对象空间分解的数据结构，即关键码范围的分解是由树中的对象决定的，并受到关键码输入的影响，因此就有可能变得非常不平衡，例如退化为线性结构。那如何来改进二叉搜索树呢？在这一模块中，你将学到Trie树、AVL树、伸展树的基本思想以及他们在具体进行插入删除操作时，是如何调整树的结构以保持平衡的。重点：Trie树的概念及其改进、AVL树的概念及插入删除操作、伸展树的概念及其旋转操作。

祝贺大家完成了《高级数据结构与算法》这门课的所有教学模块，只要顺利通过期末考试，你就向成为优秀的程序设计人员的梦想又迈进了一步哦！如果你同时也完成了《程序设计与算法》专项课程的其他部分，那么恭喜你，你已经由轻叩计算机世界大门的初学者，成长到了一名优秀的准程序员啦！快来通过期末考试，向我们的毕业项目出发，用实际的企业开发案例证明你的实力吧！