数据结构内容提要

前言

内容提要中涉及知识（概念和原理）和能力（包括写算法、写程序、分析复杂度）。

为方便学生学习，我们把内容分为“掌握”、“理解”和“了解”三级要求。“掌握”指对内容必须要理解透彻，并有运用的能力；“理解”是指对基本概念和原理能理解清楚；“了解”是知道有这个内容。

数据结构是一门极其重要的基础课程，数据结构及数据类型是对信息/数据的分类，而算法是对信息/数据的操作。没有数据结构及算法的相关知识要编写稍微复杂的程序都会感到相当困难。

对于初学者来说，这门课是非常困难的，难在要通过设计数据结构与算法来解决问题。我们把解决方法归纳为：1）有意识培养自己分析问题的能力，特别是从粗到精、从抽象到具体、从逻辑到物理的问题解决思路。这个能力对你来说终身受益，而且是人成熟的关键能力。2）掌握了问题分析的方法，就算你没有学过这门课也能写出一定细化程度的算法，但要进一步写出具有可操作性的算法，你就需要系统学习数据结构和算法，下大力气去学习和理解别人的算法，在自己脑子里有了足够的算法模式后，就容易设计出好的算法。这和“熟读唐诗三百首，不会作诗也会吟”是一个道理。3）通过实例进行手工验证你的算法程序已经是确定无误以后再编译。为什么？一方面是纠正语法错误离产生功能正确的程序还远，另一方面，只有你对自己的程序运行情况一清二楚时才可能进行有效的调试。

1.绪论

1.1数据结构的基础概念

1．理解基本概念

（1）数据（是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"）。信号也是信息的载体。信号和数据分别从电子和计算机角度来考虑。

（2）数据元素（是数据的基本单位。数据元素也称记录。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。数据项是具有含义的最小标识单位。）

（3）数据对象（性质相同的数据元素的集合）

（4）数据结构（数据元素之间存在的特定结构关系（逻辑关系或存储关系），相对于算法设计）和数据类型（一个值的集合和定义在此集合上的一组操作的总称，相对于程序设计）

例子：线性结构是数据结构,而队列、堆栈、数组都是属于线性结构的不同的数据类型

（5）基本数据类型和抽象数据类型（指由用户定义且用以表示应用问题的数据模型，通常由基本的数据类型组成，并包括一组相关服务操作）

注意区别基本数据类型（比如C语言中的字符、整型、单精度实型、双精度实型）和构造数据类型（数组、结构、联合），C语言中还有指针和空类型。

抽象数据类型的最重要特征：数据抽象（抽取本质、忽略非本质）和信息隐藏（隐藏数据存储和操作实现）

抽象数据类型三要素：数据元素、结构关系、基本操作

数据结构和抽象数据类型：（1）数据结构只突出了“结构”这一特性。（2）“数据结构”是抽象数据类型定义中的一个重要的组成部分。（3）算法事实上是抽象数据类型之上的操作。

抽象数据类型和复杂数据类型：（1）抽象数据类型的特点是抽象，再具体说是封装和隐藏（保留作为本质的接口参数，隐藏非本质的内容），（2）抽象数据类型的具体体现形式往往是复杂数据类型

1.2数据结构的内容

1．哪些数据结构研究的内容－“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）（1）哪些逻辑结构：集合结构、线性结构，树型结构（树）、网状结构（图）。另一种说法：线性和非线性

（2）哪些物理结构：顺序结构、链表结构、索性结构、散列结构。另一种说法：顺序和非顺序

（3）哪些操作：初始化、插入、删除、求长度、查找/匹配、销毁、排序、遍历、合并、替换/更新、连接

1.3算法设计

1．理解算法的定义及五个特征（有穷性、确定性、可行性、有0或多个输入、有1或多个输出）

2．理解算法设计要求（正确性、可读性、鲁棒性、高性能）。

3．理解算法和程序的不同评价标准（见课程主页）

1.4算法描述工具

1．掌握算法描述能力-类C语言，流程图（常见符号）

2．掌握算法描述规范

[包含文件]

[宏定义语句]

[自定义类型语句]

[所有子函数的原型说明]

[全局变量定义（尽量少用）][函数返回值类型]函数名([形参及说明])

{

局部变量说明；

执行语句组；

}

附带说明：

（1）自然语言和编程语言可以混合使用，随着自然语言描述用编程语言语句代替，自然语言描述可转为注释（2）使用有意义的函数名和变量名。比如GetLength,get_length,getLength，推荐学习匈牙利表示法。

（3）注意传值和传地址两种参数传递方式

（4）注意函数结果带出三种方式：全局量、函数返回值、地址传递

1.5对算法做性能评价

1．掌握算法复杂度分析能力－时间和空间复杂度

（1）采用渐进分析/极限分析

（2）n一个反映问题规模的代表值

1.6数据结构与C语言表示（数据结构与程序设计的关系）

1．了解数据结构与程序设计的关联性。采用最佳的数据结构，并采用策略方法有效地利用这些数据，便于高效解决问题

2．了解程序是在数据的特定表示方式的基础上，对抽象算法的具体描述

（1）算法＋数据结构＝程序

（2）算法+数据结构+程序设计方法+语言工具和环境＝程序

3．了解结构化程序设计。

（1）程序结构＝控制结构（顺序、选择、重复，无goto）＋数据结构

（2）通过设计结构良好的程序，提高程序执行的正确性、程序的可读性

（3）结构化程序设计方法

“自顶向下、逐步求精”的设计思想。程序设计时，应先考虑总体，后考虑细节，先考虑全局目标，后考虑局部目标。

“功能（强内聚，弱耦合）、一个入口、一个出口”的模块化结构。

“仅用三种基本控制结构”的编码方法。

4．了解面向对象程序设计方法

（1）面向对象概念：对象，类

（2）面向对象程序设计/面向对象程序设计语言的特点

封装性。就是隐藏信息。借助对象描述抽象数据类型，存储结构的说明和操作函数的说明被封装在一个整体结构中。该整体结构被称为类，而属于某个类的具体变量被称为对象。

继承性。子类具有派生它的类的全部属性（数据）和方法，而根据某一类建立的对象也都具有该类的全部

多态性。指相同名字但不同定义的函数，执行不同的操作，实现“一个接口，多种方法”。多态性的实现与静态联编、动态联编有关。静态联编支持的多态性称为编译时的多态性，也称静态多态性，它是通过重载（overload）实现的。函数重载有两种情况：一种是参数有差别的重载。另一种是参数没有差别的重载，只是他们属于不同的类。动态联编支持的多态性称为运行时的多态性，也称动态多态性，它是通过继承和虚函数实现的。

5．了解面向对象程序设计和结构化程序设计的关系

（1）无论结构化程序设计方法还是面向对象程序设计方法都是基于“需求－功能－原理－实现”的设计过程。

（2）两者无替换被替换之分。

（3）面向对象程序设计解决了结构化程序设计方法没有很好解决的"代码重用"问题。

1.7关于学习数据结构

1．了解学习数据结构的意义（为什么要学习数据结构）－解决问题和数据结构的关系（数据结构提供了造房子的预制板，见前言）

2．了解本课程和其他课程的关系－计算机专业课程体系和计算机技术人员自我培养途径

3．了解教学目的－通过设计数据结构和算法来解决实际问题（见前言）

4．了解学习方法－多看多想多写

2.线性表

从第2章到第7章，以数据结构为主线来介绍。每章先介绍逻辑结构特点，再介绍存储结构，然后再介绍其应用线性表是整个数据结构课程学习的重点。链表是整个数据结构课程的重中之重

2.1线性表的概念及其抽象数据类型定义

1．理解线性表的结构特点

（1）同一性、有穷性、有序性（具体来说，除第一及最后一个元素外，每个结点都只有一个前驱（或称前趋）和只有一个后继）。

（2）基于抽象数据结构的组成要素，进行形式化的描述。

2.2线性表的顺序存储

1．理解顺序表的特点：按逻辑次序依次存储（举例：深度和广度方式存放树）。

2．掌握顺序表的实现及操作

2.3线性表的链式存储

1．理解单链表的特点：除了存储数据，也要存储数据的位置（具体来说，要存储指示其后继结点的地址（或位置）信息，称为指针（pointer）或链（link））。

2．掌握单链表的实现及操作

3．理解头指针、头结点和首元素结点（表头结点）

（1）若无头结点，则在第一元素前插入元素或删除第一元素时（也就是涉及空表时），链表的头指针总在变化（2）有了头结点，任何数据结点的插入或删除操作都统一

4．理解循环链表、双向链表、双向循环链表、静态链表的概念

（1）注意单链表中设置头指针、循环链表中设置尾指针而不设置头指针的各自好处。

5．掌握链表图的画法

（1）链表图提供了针对算法的图形化、精细描述，有利于写出程序。

（2）其实，四种物理结构的图都要会画。顺序表的图比较简单，链表的图最常用，索引表和哈希表的图在本课程中出现较少

（3）画链表图的好处有两个，设计算法（帮助分析算法细节）和检验算法（检查现有算法的正确性）。

（4）注意上课时老师的讲解，教材和课件上是有错误的。

6．掌握算法设计能力

（1）先形式后内容。函数名和参数等先写好

（2）执行语句组分三段：输入、处理、输出（3）先自然语言再编程语言

（4）等到算法细致到一定程度就要考虑数据类型和结构

（5）用例子（画物理结构图）引出思路，从粗线条的思路到细线条的算法，用例子（画物理结构图）引来检验算法

（6）考虑特殊、极端、非法情况来检查算法的正确性和鲁棒性。比如动态产生和删除结点，在头部或者尾部操作是否特殊（主要是针对头指针和尾指针），表空的情况。

（7）常见例子：两个链表归并、对链表进行倒序

2.4线性表应用——一元多项式的表示及相加

1．理解这个例子

2.5顺序表与链表的综合比较

1．理解顺序表和链表的比较

顺序表链表

线性关系如何体现基于相邻存储的先后位置指针

是否能随机存储能否

时间复杂度插入删除差，查找好插入删除好，查找差

动态和静态不是区分顺序表和链表的特征

顺序表链表

静态通常所说的顺序表就是静态顺序表

动态通常所说的链表就是动态链表

3.栈和队列

从数据结构角度讲，栈和队列也是线性表，其操作是线性表操作的子集，属操作受限的线性表。

队头（front），队尾（rear），栈顶（top），栈底（bottom），线性表头（head），线性表尾（tail）。

3.1栈1．理解栈的特点：先进后出

2．掌握栈的实现及操作

（1）顺序栈，链栈，多栈、共享栈

3．理解栈的应用

（1）利用栈进行括号匹配、表达式求值的原理

（2）（不作要求）借助栈将递归转向于非递归的算法

（3）（不作要求）中缀表达式和前缀、后缀表达式之间的转换

（4）（不作要求）串中心对称的判定，二叉树遍历的递归和非递归算法，图的深度优先遍历

4．掌握递归原理

（1）利用局部和全部的相似性，有分解

（2）有出口

3.2队列

1．理解队列的特点：先进先出

2．掌握队列的实现及操作

（1）循环队列，链队列

（2）栈和队列较多采用顺序表，而不是链表，为什么？

（2）入队在头还是尾？

3．理解队空和队满

（1）链队列空的条件是首尾指针相等，没有链队列满

（2）循环顺序队列满的判定条件是队尾加1等于队头（注意取模运算），循环顺序队列空的判定条件是队尾等于队头。

4．理解队列的应用

（1）利用队列打印杨辉三角、键盘输入缓冲区的原理

（2）（不作要求）树的层次遍历、图的宽度优先遍历

4.串

4.1串的基本概念

1．理解串的概念：串是数据元素为字符的线性表

（1）空串与空格串的区别

（2）串相等的条件

（2）字符串和串的区别

2．了解C语言中有哪些字符串函数（如取子串，串连接，串替换，求串长）

4.2串的存储实现

1．理解定长顺序串、堆串、链串、块链串

4.3串的应用举例：简单的行编辑器

1．理解这个例子

5.数组和广义表

数组和广义表是两类特殊的线性结构，主要体现在其数据元素又是一个数据结构。注意有些书上把它们归入非线性结构。

5.1数组的定义和运算

1．了解：二维数组可以定义为“其数据元素为一维数组（线性表）”的线性表。数组以此类推。

2．了解列向量和行向量

3．理解：数组的操作一般只有两类（为什么？因为数组中元素的个数固定）

（1）获得特定位置的元素值；

（2）修改特定位置的元素值。

5.2数组的顺序存储和实现

1．掌握（2维或3维）数组中某数组元素的position求解（行序为主或列序为主）

5.3特殊矩阵的压缩存储

1．理解三角矩阵（分成下三角矩阵、上三角矩阵、对称矩阵三类）、（三对角）带状矩阵、稀疏矩阵的特点2．掌握特殊矩阵中某数组元素的position求解（行序为主或列序为主）

3．理解稀疏矩阵的存储方式：三元组表，十字链表存储

（1）（不作要求）基于三元组表进行矩阵的转置和乘法等运算

（2）（不作要求）将稀疏矩阵的三元组向十字链表进行转换

5.4广义表

1．理解广义表的相关概念

（1）广义表是线性表的推广。即广义表中放松对表元素的原子，容许它们具有其自身结构（每个子表或元素也是线性结构）。

（2）广义表的定义采用递归定义

（2）广义表的长度、子表、表头与表尾。特别应该理解表头与表尾的定义，一个广义表看作是表头和表尾两部分2．（不作要求）理解广义表的存储结构：头尾链表、扩展线性链表

3．（不作要求）掌握广义表的操作实现

6.树和二叉树

6.1树的定义与基本术语

1．理解树的相关定义：树（用了递归定义）、根、子树、空树

2．掌握树的四种图解表示法

3．理解树的相关术语：结点、结点的度、叶结点（也称为终端结点）、分支结点（也称为非终端结点）、孩子结点、双亲结点、兄弟结点、祖先结点、子孙结点、树的度、结点的层次、树的高度（深度）、有序树、森林

6.2二叉树

1．理解二叉树的相关定义：二叉树、完全二叉树、满二叉树

（1）二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不可交换的（不同于普通的双分支树）。

2．掌握二叉树五大性质及证明

（1）第i层的最多结点数，

（2）深度为k的二叉树的最多结点数，

（3）n0=n2+1的性质，

（4）n个结点的完全二叉树的深度，（5）顺序存储二叉树时孩子结点与父结点之间的换算关系（左为：2*i，右为：2*i+1）。

3．理解二叉树的存储结构：顺序和链式

（1）（不作要求）顺序存储结构和二叉链表存储结构的各自优缺点及相互转换

（2）（不作要求）二叉树的三叉链表表示方法

6.3二叉树的遍历与线索化

1．理解遍历的概念和作用

（1）按照一定规律对二叉树中的每个结点访问且仅访问一次

（2）遍历操作是其他操作的基础，如求叶子个数，求二叉树结点总数，求二叉树的高度，求各结点的层次数，求度为0、1、2的结点数，复制二叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点等等的算法。

2．掌握二叉树遍历的递归算法：前、中、后序方法(前序又叫先序)。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。

（1）由二叉树的遍历的前序和中序序列或后序和中序序列可以唯一构造一棵二叉树，由前序和后序序列不能唯一确定一棵二叉树。

3．（不作要求）理解二叉树的遍历的非递归算法

（1）基于栈的递归消除

4．理解线索二叉树的特点

（1）利用二叉链表中的空链域，将遍历过程中结点的前驱、后继信息保存下来。指向前驱和后继结点的指针叫做线索

（2）线索二叉树的引出，是为避免如二叉树遍历时的递归求解。

（3）二叉树线索化的实质是建立结点在相应序列（前、中或后序）中的前驱和后继之间的直接联系。5．（不作要求）掌握三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点，线索二叉树中结点的插入、删除）。

6.4树、森林和二叉树的关系

1．理解树的三种存储结构：双亲表示法、孩子表示法、孩子兄弟表示法

2．理解树、森林与二叉树的相互转化方法

3．理解树与森林的遍历方法

（1）树的遍历方法：先根遍历、后根遍历

（2）森林的遍历方法：先序遍历、中序遍历、后序遍历

（3）理解树与森林的遍历算法及其与二叉树遍历算法的联系。先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。

（4）二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也是利用二叉链表存储孩子及兄弟。

6.5哈夫曼树及其应用

1．理解相关术语：路径和路径长度，结点的权和带权路径长度、树的带权路径长度

（1）什么样的树的带权路径长度最小－>引出哈夫曼树

2．理解哈夫曼树（即最优二叉树）定义和构造原理

3．理解哈夫曼编码原理

（1）利用哈夫曼树，可以设计出最优的前缀编码。

（2）前缀编码:任一个字符的编码都不是另一个字符的编码的前缀假如有A，B，C，D四个字符,设计的前缀编码分别为0,10,110,111,任一个的编码都不是另一个编码的前缀.7.图

7.1图的定义与基本术语

1．了解图的形式化定义：图

2．理解图的相关术语：无向图，有向图，弧，边，完全图，子图，（强）连通图，（强）连通分量

3．理解邻接点的相关术语：邻接点，相邻接，相关联

4．理解路径的相关术语：路径，路径长度，回路或环，简单路径，简单回路

5．理解度的相关术语：度，入度，出度

6．理解权与网的相关术语：权，赋权图或网

7．理解生成树的相关术语：生成树（极小连通子图）

7.2图的存储结构

1．掌握图的邻接矩阵和（逆）邻接表存储形式。

2．理解图的十字链表及邻接多重表存储形式。

7.3图的遍历

1．掌握深度遍历和广度遍历原理。这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。

（1）（不作要求）图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如：“求最长的最短路径问题”和“判断两顶点间是否存在长为K的简单路径问题”，就分别用到了广度遍历和深度遍历算法。

7.4图的应用

1．理解最小生成树的定义，掌握构造算法原理（包括PRIM算法和KRUSKAL算法）

2．掌握拓扑排序原理

（1）有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。当然，后一种排序出来的结果是“逆拓扑有序”的。

3．掌握关键路径原理

（1）理解关键路径的关键有三个方面：一是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。

（2）（不作要求）在实际设计关键路径的算法时，还应该注意采用邻接表的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早时间全部置为0。关键路径问题是工程进度控制的重要方法，具有很强的实用性。

4．掌握最短路径算法原理

（1）最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。

（2）最短路径具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法，解决第二个问题用FLOYD算法。

8.查找

从第8章到第10章，以算法为主线来介绍。

现实生活中，search几乎无处不在，特别是现在的网络时代，search占据了我们上网的大部分时间。

8.1查找的基本概念

1．理解基本概念：列表，（主、次）关键字，查找，（查找成功时的）平均查找长度ASL

2．（学完总结）理解各种查找算法的特点、优缺点和ASL

（1）比较式查找法（基于线性表的查找，基于树的查找）和计算式查找法（哈希查找法）

8.2基于线性表的查找法

1．理解在三种线性结构（顺序表，有序顺序表，索引顺序表）上的查找算法：顺序查找法、折半查找法、分块查找法。

（1）对于第一种，我们采用传统查找方法，逐个比较。对于有序顺序表我们采用二分查找法。对于第三种索引结构，我们采用索引查找算法。

2．掌握在各种线性表查找算法中ASL的计算方法

8.3基于树的查找法

1．了解树表的几种形式：二叉排序树，平衡二叉树，B树，键树。

（1）（不作要求）键树也称字符树，特别适用于查找英文单词的场合。

2．掌握二叉排序树的构造和查找原理

（1）二叉排序树，简言之，就是“左小右大”，它的中序遍历结果是一个递增的有序序列。

（2）（不作要求）对于二叉排序树，“判断某棵二叉树是否二叉排序树”这一算法经常被考到，可用递归，也可以用非递归。

3．理解平衡二叉树的概念

（1）平衡二叉树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡二叉树对左右子树的深度有了限定：深度之差的绝对值（即平衡因子）不得大于1。

（2）（不作要求）理解平衡二叉树的四种失衡调整算法，调整的一个参照是：调整前后的中序遍历结果相同。4．理解m路查找树和B树的概念

（1）B树是二叉排序树的进一步改进，也可以把B树理解为三叉、四叉....排序树。

（2）（不作要求）除B树的查找算法外，应该特别注意一下B树的插入和删除算法。因为这两种算法涉及到B 树结点的和合并，是一个难点。

5．了解在各种树表的查找算法中的ASL

8.4计算式查找法——哈希法

1．理解“哈希”法的原理

（1）哈希一词，是外来词，译自“hash”一词，意为：散列或杂凑的意思。

（2）与顺序表、链表进行对比，理解索引表和散列表的原理和好处

（3）哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个function，该函数对关键字进行转换后，其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。

2．理解哈希函数/哈希表的几种构造方法3．理解处理冲突的几种方法

4．了解在哈希查找算法中的ASL

9.内部排序

9.1排序的基本概念

1．理解排序的概念

（1）内部排序和外部排序

（2）稳定性

（3）排序中的基本操作：比较和移动

（4）待排序数据的存储结构：向量结构（顺序结构），链表结构，地址向量＋记录向量

9.2插入类排序

1．理解插入排序基本思想

2．掌握各类插入排序的原理：直接插入、折半插入、希尔排序。

（1）这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找。希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。

3．了解各类插入排序的时间复杂度和稳定性

9.3交换类排序法

1．理解交换排序基本思想

2．掌握各类插入排序的原理：冒泡排序、快速排序

（1）快速排序的思想是：用中间数将待排数据组一分为二。快速排序，在处理的“问题规模”这个概念上，与希尔有点相反，快速排序，是先处理一个较大规模，然后逐渐把处理的规模降低，最终达到排序的目的。

3．了解各类交换排序的时间复杂度和稳定性

9.4选择类排序法

1．理解选择排序基本思想

2．掌握各类选择排序的原理：简单选择、树形选择、堆排序

（1）这三种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数；树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大（小）者，最终选出最小（大）数；而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。

3．了解各类选择排序的时间复杂度和稳定性

9.5归并排序

1．理解归并排序基本思想

（1）归并排序通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。

2．掌握2路归并排序的原理

3．了解2路归并排序的时间复杂度和稳定性

（1）归并排序是稳定排序。

9.6分配类排序（又称为基数排序）

1．理解各类分配排序的原理：多关键字排序，链式基数排序

（1）基数排序比较适合于一些特别的场合，比如扑克牌排序问题等。

（2）基数排序分为两种：多关键字的排序（扑克牌排序），链式排序（整数排序）。

（3）基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。

2．了解各类分配排序的时间复杂度和稳定性

9.7各种排序方法的综合比较

1．了解：比较各种排序算法的特点、其优缺点（比如是否稳定）和性能指标（时间复杂度）

（1）插入、选择、交换、归并、基数等五种排序方法