04算法与基本数据结构

1、n1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。n2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。n3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。n4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。n5. 线性单链表、双向链表与循环链表的结构及其基本运算。n6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。n7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。n 基本概念基本概念n 基本数据结构基本数据结构n 查找与排序查找与排序数据：数据：

2、是对客观事物的符号表示，在计算是对客观事物的符号表示，在计算机科学中是指能输入到计算机中并机科学中是指能输入到计算机中并被计算机存储、加工的符号总称。被计算机存储、加工的符号总称。数据元素：数据元素：是数据的基本单位，由若干个数据是数据的基本单位，由若干个数据项组成，在程序中作为一个整体而加以项组成，在程序中作为一个整体而加以考虑和处理。数据元素具有完整确定的考虑和处理。数据元素具有完整确定的实际意义，有时也称为实际意义，有时也称为元素、结点、顶元素、结点、顶点或记录点或记录结构：结构：是数据元素之间的关联关系是数据元素之间的关联关系数据结构数据结构：数据结构带有结构的同性质数据元数据结构带有

3、结构的同性质数据元素的集合素的集合数据结构包括以下三方面内容：数据结构包括以下三方面内容： 逻辑结构、存储结构和对数据结构的操作逻辑结构、存储结构和对数据结构的操作 v 逻辑结构：逻辑结构：数据元素之间逻辑上的关系，它数据元素之间逻辑上的关系，它是数据的组织形式。通常将数据的逻辑结构是数据的组织形式。通常将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构线性结构和非线性结构。 具体可分为四类：具体可分为四类： 其中其中 、为非线性结构、为非线性结构集合集合 线性结构线性结构 树型结构树型结构 图状结构图状结构v 存储结构：存储结

4、构：数据元素以及数据元素之间的数据元素以及数据元素之间的逻辑关系在计算机内存中的表示。逻辑关系在计算机内存中的表示。v 一般地，一个存储结构包括以下两个主要部分：一般地，一个存储结构包括以下两个主要部分： 存储结点存储结点( (简称结点简称结点),),每个结点存放一个数据元素每个结点存放一个数据元素 数据元素之间关系的表示，也就是逻辑结构的计算机数据元素之间关系的表示，也就是逻辑结构的计算机内部表示内部表示常用的数据存储结构：常用的数据存储结构：顺序顺序存储方法存储方法链式链式存储方法存储方法索引索引存储方法存储方法散列散列存储方法存储方法v 数据的运算如查找、排序、增加、修改、删除数据的运算

5、如查找、排序、增加、修改、删除各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的数据的存储结构数据的存储结构链式存储结构是在每个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系算法：算法：算法是对具体问题求解过程和步骤的一种描述算法是对具体问题求解过程和步骤的一种描述，简单地说，就是解决问题的操作步骤。，简单地说，就是解决问题的操作步骤。算法四个基本特征：算法四个基本特征：有穷性：算法在特定的执行环境中执行应当能够得出 满意的结果，即必须有一个或多个输出。确定性：对算法中的每一步的描述是明确的，无歧义 可行性：算法中的操作步骤为有限个，且每个步骤都能在有限时间内

6、完成。拥有足够的情报：算法在拥有足够的输入信息和初始化信息时，才是有效的；当提供的情报不够时，算法可能无效。n算法通常由两个基本要素组成： 对数据对象的运算和操作 算法的控制结构n算法复杂度包括： 时间复杂度：指执行算法时所需要的计算工作量，通常是用算法所执行的基本运算次数来度量。注：算法程序执行的具体时间和算法的时间复杂度并不是一致的。 空间复杂度：指执行这个算法所需要的内存空间。算法的描述算法的描述用自然语言表示算法：用自然语言表示算法：就是用人们所熟悉的就是用人们所熟悉的自然语言把算法的各个步骤依次表示出来。自然语言把算法的各个步骤依次表示出来。 用流程图表示算法：用流程图表示算法：就是

7、用一些大家共识的就是用一些大家共识的专用图形符号和带有箭头的流程线来表示算专用图形符号和带有箭头的流程线来表示算法。法。 用程序设计语言表示算法：用程序设计语言表示算法：用计算机能理解用计算机能理解和执行的程序设计语言把算法表示出来，然和执行的程序设计语言把算法表示出来，然后把程序输入计算机并执行，计算机才能按后把程序输入计算机并执行，计算机才能按照预定的算法去解决问题。照预定的算法去解决问题。 算法设计要求：算法设计要求：正确性正确性 可读性可读性 健壮性健壮性效率高与低存储需求效率高与低存储需求 线性表线性表: : 是是n(nO)n(nO)个同类型数据元素个同类型数据元素( (结点结点)

8、)的有的有穷序列。其中数据元素的个数穷序列。其中数据元素的个数n n称为线性称为线性表的长度表的长度( (简称表长简称表长) )。表长为。表长为O O的线性表的线性表称为空表。称为空表。表示成：表示成：(a(a1 1，a a2 2 ，a an n) ) 线性表逻辑结构的基本特征线性表逻辑结构的基本特征: : 存在存在惟一惟一的一个被称为的一个被称为“第一个第一个”的数据元素的数据元素和和惟一惟一的一个被称为的一个被称为“最后一个最后一个”的数据元素；的数据元素； 除第一个数据元素外，其他数据元素有且仅有除第一个数据元素外，其他数据元素有且仅有一个一个直接前趋直接前趋元素；元素； 除最后一个数据

9、元素外，其他数据元素有除最后一个数据元素外，其他数据元素有且仅且仅有一个直接后继有一个直接后继元素。元素。顺序表是用一组地址连续的存储单元依次存顺序表是用一组地址连续的存储单元依次存储线性表的各个数据元素。储线性表的各个数据元素。元素元素a a1 1a a2 2a a3 3a ai-1i-1a ai ia ai+1i+1a an n相对相对地址地址0 01 12 2i-2i-2i-1i-1i in-1n-1特点：特点：逻辑结构中相邻的结点在存储结构中仍相邻逻辑结构中相邻的结点在存储结构中仍相邻应用范围：应用范围：适合于小线性表或者建立之后其适合于小线性表或者建立之后其中元素不常变动的线性表，而

10、不适合中元素不常变动的线性表，而不适合用于需要经常进行插入和删除运算的用于需要经常进行插入和删除运算的线性表和长度较大的线性表。线性表和长度较大的线性表。 (1) (1) 插入：插入：在表的第在表的第i(1in+1)i(1in+1)个位置上，插入一个个位置上，插入一个新结点新结点x x，使线性表的长度加，使线性表的长度加1 1 。基本步骤为：。基本步骤为： 将结点将结点a ai ia an n各后移一个位置各后移一个位置, ,以便空出第以便空出第i i个位置；个位置； 将新结点将新结点x x置入第置入第i i个位置；个位置； 表长加表长加l l元素元素a a1 1a a2 2a a3 3a a

11、i-1i-1a ai ia ai+1i+1a an n相对地相对地址址0 01 12 2i-2i-2i-1i-1i in-1n-1(2) (2) 删除：删除：将表的第将表的第i(1in)i(1in)个结点删去，个结点删去，使线性表的长度减使线性表的长度减1 1。基本步骤为：。基本步骤为： 结点结点a ai i+1+1a an n依次前移一个位置依次前移一个位置( (覆盖被删结点覆盖被删结点a ai i) )； 表长减表长减1 1元素元素a a1 1a a2 2a a3 3a ai-1i-1a ai ia ai+1i+1a an n相对地址相对地址0 01 12 2i-2i-2i-1i-1i i

12、n-1n-1是用一组任意的存储单元来存放线性表的结点。是用一组任意的存储单元来存放线性表的结点。 单链表的结点单链表的结点( (每个存储单元每个存储单元) )由由数据域数据域(data)(data)和和指指针域针域(next)(next)两部分组成；两部分组成；数据域数据域用于存储线性表用于存储线性表一个数一个数据元素据元素；指针域指针域用于存放用于存放一个指针一个指针，该，该指针指向指针指向其直接其直接后继结点。这样，所有结点通过指针链接起来后继结点。这样，所有结点通过指针链接起来, ,因此链因此链表中结点的逻辑次序和物理次序不一定相同表中结点的逻辑次序和物理次序不一定相同a1anhead特

13、点：特点：指针为数据元素之间的逻辑关系的映像指针为数据元素之间的逻辑关系的映像循环链表是一种首尾相接的链表循环链表是一种首尾相接的链表 双向链表双向链表, ,就是在单链表的每个结点里再增加一个就是在单链表的每个结点里再增加一个指向其直接前趋的指针域指向其直接前趋的指针域prior,prior,这样形成的链表就有这样形成的链表就有两条不同方向的链两条不同方向的链。双双( (向向) )循环链表：循环链表：头尾相链接的双向链表头尾相链接的双向链表a1 a2anhead a1a2anhead(1)(1)插入：插入：基本步骤如下：基本步骤如下： 在单链表上找到插入位置；在单链表上找到插入位置； 生成一个

14、值为生成一个值为x x的新结点；的新结点； 将新结点插入将新结点插入 假定指针假定指针p p指向单链表中的第指向单链表中的第i-1i-1个结点，个结点，s s指向已生成的新结点，在指向已生成的新结点，在单链表上插入结点单链表上插入结点s s的操作过程如图的操作过程如图所示。基本操作语句为：所示。基本操作语句为： p ps s(2)(2)删除：删除：基本步骤如下：基本步骤如下： 找到第找到第i i个结点；个结点； 从单链表上摘除该结点。从单链表上摘除该结点。 假定假定指针指针p p指向待删结点的前一个结点，指向待删结点的前一个结点，q q指指向待删结点，删除操作用向待删结点，删除操作用c c语言

15、描述如下：语言描述如下： ；执行执行free(q)free(q)的结果是释放的结果是释放q q所指结点占用的内存所指结点占用的内存空间。若在删除算法中无此语句，则结点空间。若在删除算法中无此语句，则结点q q虽已不虽已不在单链表上，但仍被用户程序闲置性占用。在单链表上，但仍被用户程序闲置性占用。 xyzpq栈和队列都是操作受限的线性表栈和队列都是操作受限的线性表栈底栈底栈顶栈顶入栈入栈出栈出栈a1a2an 栈的逻辑结构和线性表相同，但是，栈栈的逻辑结构和线性表相同，但是，栈(Stack)(Stack)是仅限在表的是仅限在表的进行插入和删除运算进行插入和删除运算的线性表，通常称插入、删除这一端为

16、的线性表，通常称插入、删除这一端为栈顶栈顶，另，另一端称为一端称为栈底栈底, ,表中无元素时为表中无元素时为空栈空栈栈栈栈的运算原则是栈的运算原则是“先进后出先进后出” 插入运算称为进栈插入运算称为进栈( (或入栈或入栈) ) 删除运算称为退栈删除运算称为退栈( (或出栈或出栈) )基本运算为：基本运算为： 入栈、出栈、取栈顶元素入栈、出栈、取栈顶元素栈的特点：栈的特点： （1 1）栈顶元素总是最后被插入的元素，也是）栈顶元素总是最后被插入的元素，也是最早最早被删被删除的元素。除的元素。 （2 2）栈底元素总是最早被插入的元素，也是）栈底元素总是最早被插入的元素，也是最晚最晚被删被删除的元素。

17、除的元素。 （3 3）栈具有）栈具有记忆记忆作用。作用。 （4 4）在顺序存储结构下，栈的插入与删除运算都）在顺序存储结构下，栈的插入与删除运算都不需不需要要移动其他元素。移动其他元素。 （5 5）栈顶指针）栈顶指针TopTop动态动态反映了栈中元素的变化情况。反映了栈中元素的变化情况。栈栈栈栈v顺序栈的进栈运算顺序栈的进栈运算 将入栈元素放入到栈顶将入栈元素放入到栈顶下标所指的位置上下标所指的位置上, ,栈顶栈顶下标加下标加l l v顺序栈的退栈运算顺序栈的退栈运算 退栈先将栈顶下标减退栈先将栈顶下标减1 1，再将栈顶元素取出再将栈顶元素取出栈底栈底栈顶栈顶入栈入栈出栈出栈a1a2an 队列

18、队列(Queue)(Queue)，两头都有，两头都有限制限制，插入只能在，插入只能在表的一端进行表的一端进行( (只进不出只进不出) )，而删除只能在表的另，而删除只能在表的另一端进行一端进行( (只出不进只出不进) )，进行插入操作的端称为队进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。素时，称为空队列。 。q 队列的操作原则是队列的操作原则是先进先出先进先出q 队列的顺序存储一般采用循环队列的顺序存储一般采用循环队列。把队列设想成一个循环队列。把队列设想成一个循环表，即设想数组首尾相连。这表，即设想数组首尾相连。

19、这种存储结构称为循环队。通常种存储结构称为循环队。通常frontfront指向指向队头元素的前一个队头元素的前一个位置，位置，realreal指向指向队尾元素队尾元素ABCDEFG树树是是n(n0)n(n0)个结点的有限集合。个结点的有限集合。在任意一棵非空树中在任意一棵非空树中: : 有且仅有一个特定的称为根的结点：有且仅有一个特定的称为根的结点： 当当nlnl时，其余结点分为时，其余结点分为m(m0)m(m0)个互不相交的非空集个互不相交的非空集合合T1T1，T2T2，TmTm，其中每一个集合本身又是一棵，其中每一个集合本身又是一棵树，并称为根的子树。树，并称为根的子树。 树是一种树是一种

20、“”结构。所谓结构。所谓“分支分支”是指树是指树中任一结点的子孙可以按它们所在的子树的不同而中任一结点的子孙可以按它们所在的子树的不同而划分成不同的划分成不同的“分支分支”；所谓；所谓“层次层次”是指树上所是指树上所有结点可以按它们的层数划分成不同的有结点可以按它们的层数划分成不同的“层次层次”ABCDEFG(1)(1)树上任一结点所拥有的子树的数目称为该结点的树上任一结点所拥有的子树的数目称为该结点的。度为度为0 0的结点称为的结点称为。度大于。度大于O O的结点的结点称为称为非非。一棵树中所有结点的。一棵树中所有结点的度的最大值称为该度的最大值称为该。(2)(2)若树中结点若树中结点A A

21、是结点是结点B B的直接前趋，则称的直接前趋，则称A A为为B B的的或父结点，称或父结点，称B B为为A A的的。父结点相同的。父结点相同的结点互称为结点互称为。一棵树上的任何结点。一棵树上的任何结点( (不包括根本不包括根本身身) )称为根的称为根的。反之，若。反之，若B B是是A A的子孙，则称的子孙，则称A A是是B B的的。(3)(3)结点的层数结点的层数( (或深度或深度) )从根开始算起：根的层数为从根开始算起：根的层数为l l，其余结点的层数为其双亲的层数加其余结点的层数为其双亲的层数加l l。一棵树中所有。一棵树中所有结点层数的最大值称为该结点层数的最大值称为该。 ABCDE

22、FG：是结点的有穷集合，它或者是空集，或者是结点的有穷集合，它或者是空集，或者同时满足下述两个条件：同时满足下述两个条件： 有且仅有一个称为根的结点；有且仅有一个称为根的结点； 其余结点分为两个互不相交的集合其余结点分为两个互不相交的集合T1T1、T2T2，T1T1与与T2T2都是二叉树，并且都是二叉树，并且TlTl与与T2T2有顺序关系有顺序关系(T1(T1在在T2T2之前之前) )，它们分别称为，它们分别称为根的左子树和右子树。根的左子树和右子树。 二叉树的每个结点至多只有两棵子树，并且这二叉树的每个结点至多只有两棵子树，并且这两棵子树之间有次序关系。二叉树上任一结点左、两棵子树之间有次序

23、关系。二叉树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子。右子树的根分别称为该结点的左孩子和右孩子。ABCDEFG的的特点：特点： （1 1）二叉树可以为空，空的二叉树没有结点，）二叉树可以为空，空的二叉树没有结点，非空二叉树有且只有一个根结点。非空二叉树有且只有一个根结点。 （2 2）每个结点最多有两颗子树，即二叉树中不）每个结点最多有两颗子树，即二叉树中不存在度大于存在度大于2 2的结点。的结点。 （3 3）二叉树的子树有左右之分，其次序不能任）二叉树的子树有左右之分，其次序不能任意颠倒。意颠倒。二叉树有二叉树有基本形态，如图所示基本形态，如图所示二叉树的基本性质二叉树的基本性质

24、 二叉树第二叉树第i(i1)i(i1)层上至多有层上至多有2 2i-1i-1个结点。个结点。 深度为深度为k(k1)k(k1)的二叉树至多有的二叉树至多有2 2k k-1-1个结点。个结点。 对任何一棵二叉树，如果其终端结点数为对任何一棵二叉树，如果其终端结点数为n n0 0，度，度为为2 2的结点数为的结点数为n n2 2，则，则n n0 0 = n = n2 2+1+1。 空树空树 只有根节点只有根节点 只有左子树只有左子树 只有右子树只有右子树 有左右子树有左右子树q 满二叉树满二叉树 一棵深度为一棵深度为k(k1)k(k1)且有且有2 2k-1k-1个结点的二个结点的二叉树称为叉树称为

25、满二叉树满二叉树，这种树的特点是每一层，这种树的特点是每一层上的结点数都是最大结点数。如图所示。上的结点数都是最大结点数。如图所示。q 完全二叉树完全二叉树 深度为深度为k(k1)k(k1)有有n n个结点的二叉树，当且个结点的二叉树，当且仅当其每一个结点都与深度为仅当其每一个结点都与深度为k k的满二叉树中编的满二叉树中编号从号从1 1至至n n的结点一一对应时，称之为的结点一一对应时，称之为完全二叉树完全二叉树。如图所示。如图所示。具有具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为loglog2 2n+ln+l。除最后一层外，每一层上的结点数均达到最大值。满二叉树也是完全二

26、叉树，反之不一定。 如果将一棵有如果将一棵有n n个结点的完全二叉树按层编号，则对个结点的完全二叉树按层编号，则对任一编号为任一编号为i(1in)i(1in)的结点的结点x x有：有：若若i=li=l，则结点，则结点x x是根，无双亲；若是根，无双亲；若i1i1，则，则x x的双亲结的双亲结点点P P的编号为的编号为i/2i/2。若若2in2in，则结点，则结点x x无左孩子无左孩子( (且无右孩子且无右孩子) )；否则，；否则，x x的的左孩子的编号为左孩子的编号为2i2i。若若2i+1n2i+1n，则结点，则结点x x无右孩子；否则，无右孩子；否则，x x的右孩子的编的右孩子的编号为号为2

27、i+12i+1。二叉树的顺序存储二叉树的顺序存储 将一棵树中的所有将一棵树中的所有n n个结点按层编号，将编号为个结点按层编号，将编号为i i的结的结点存入一维数组的第点存入一维数组的第i i个单元。个单元。 若二叉树不是完全二叉树，则通过在非完全二又树的若二叉树不是完全二叉树，则通过在非完全二又树的“残缺残缺”位置上增设位置上增设“虚结点虚结点”将其转化为完全二叉树。将其转化为完全二叉树。 用顺序存储方式对于完全二叉树而言其结构简单又节用顺序存储方式对于完全二叉树而言其结构简单又节省空间，但是对于一般二叉树并不合适。省空间，但是对于一般二叉树并不合适。二叉树的二叉树的结点结构中设两个指针域结

28、点结构中设两个指针域和和分别指向该分别指向该结点的结点的和和，另有一个数据域另有一个数据域存放结点数存放结点数据，加上一个指向根结点的指针就构成了二叉树的链式存据，加上一个指向根结点的指针就构成了二叉树的链式存储结构，称为二叉链表。由根指针唯一确定的。储结构，称为二叉链表。由根指针唯一确定的。二叉树的遍历：二叉树的遍历：就是按某种次序就是按某种次序“访问访问”二叉树上的二叉树上的所有结点，使得每个结点被访问一次，而且仅被访问一所有结点，使得每个结点被访问一次，而且仅被访问一次。次。 二叉树是由三个基本单元组成：二叉树是由三个基本单元组成：。因此，若能依次遍历这三部分，便是遍历了整。因此，若能依

29、次遍历这三部分，便是遍历了整个二叉树。假如以个二叉树。假如以L L、D D、R R分别表示遍历左子树、访问根分别表示遍历左子树、访问根结点和遍历右子树，则可有结点和遍历右子树，则可有DLRDLR、DRLDRL、LDRLDR、LRDLRD、RDLRDL、RLD 6RLD 6种遍历二叉树方案。若限定先左后右，则只有种遍历二叉树方案。若限定先左后右，则只有DLRDLR、LDRLDR、LRDLRD三种情况，分别称之为三种情况，分别称之为(1)(1)先根（先根（前序前序）遍历）遍历 访问根结点；访问根结点； 先根遍历左子树；先根遍历左子树； 先根遍历右子树。先根遍历右子树。(2)(2)中根（中根（中序中

30、序）遍历）遍历 中根遍历左子树；中根遍历左子树； 访问根结点；访问根结点； 中根遍历右子树。中根遍历右子树。(3)(3)后根（后根（后序后序）遍历）遍历 后根遍历左子树；后根遍历左子树； 后根遍历右子树；后根遍历右子树； 访问根结点访问根结点 下图二叉树的三种遍历序列下图二叉树的三种遍历序列 先根遍历序列：先根遍历序列：1、2、4、8、9、5、10、11、3、6、12、7 中根遍历序列：中根遍历序列：8、4、9、2、10、5、11、l、12、6、3、7 后根遍历序列：后根遍历序列：8、9、4、10、11、5、2、12、6、7、3、1以顺序表作为存储结构以顺序表作为存储结构查找过程：查找过程：从

31、表中最后一个（或第一个）记录开始，从表中最后一个（或第一个）记录开始，逐个进行记录的关键字和给定值的比较，若某个记逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，录的关键字和给定值比较相等，则查找成功则查找成功；反之，；反之，若直至第一个记录，其关键字和给定值比较都不等，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，则表明表中没有所查记录，查找失败查找失败。时间复杂度分析：时间复杂度分析：（1）第一个元素就是要查找的元素，则比较次数为1次。（2）最后一个元素是要找的元素，或者在线性表中，没有要查找的元素，则需要与线性表中所有的元素比较，比较次数为

32、n次。（3）需要比较n/2次。因此查找算法的时间复杂度为O(n)。当线性表为无序表，不管何种存储结构，只能用顺序查找。即使是有序线性表，如果采用链式存储结构，也只能用顺序查找 “有序有序”是特指元素按非递减排列，即从小到大是特指元素按非递减排列，即从小到大排列，但允许相邻元素相等。排列，但允许相邻元素相等。二分查找法的基本思想是：二分查找法的基本思想是：每次将处于查找区间中每次将处于查找区间中间位置上的间位置上的数据元素的键值数据元素的键值x x与与给定值给定值K K比较，若不比较，若不等则缩小查找区间等则缩小查找区间( (若若K K比中间值大则舍弃下半部分，比中间值大则舍弃下半部分，若若K

33、K比中间值小则舍弃上半部分比中间值小则舍弃上半部分) )并在新的区间内重并在新的区间内重复上述过程，直到查找成功或查找区间长度为复上述过程，直到查找成功或查找区间长度为0 0( (即即查找不成功查找不成功) )为止。为止。 当有序表的长度为当有序表的长度为n n时，时间复杂度为时，时间复杂度为 o(logo(log2 2n)n)，即在最坏的情况下，二分查找只需比较即在最坏的情况下，二分查找只需比较 次。次。使用二分查找的线性表满足两个条件：用顺序存储结构线性表是有序表n2log（1 1）交换类排序法：借助数据元素的）交换类排序法：借助数据元素的“交换交换” 来进来进行的一种方法。行的一种方法。

34、 （A A）冒泡排序法）冒泡排序法 （B B）快速排序法）快速排序法（2 2）插入类排序方法：每次将一个待排序的元素，）插入类排序方法：每次将一个待排序的元素，按其元素值的大小插入到前面已经排好序的子表按其元素值的大小插入到前面已经排好序的子表中的适当位置，直到全部元素插入完成为止。中的适当位置，直到全部元素插入完成为止。 （A A）简单插入排序法）简单插入排序法 （B B）希尔排序法）希尔排序法（3 3）选择类排序法：通过每一趟从排序序列中选出）选择类排序法：通过每一趟从排序序列中选出值最小的元素，顺序放在已排好序的有序子表的值最小的元素，顺序放在已排好序的有序子表的后面，直到全部序列满足排

35、序要求为止。后面，直到全部序列满足排序要求为止。 （A A）简单选择排序法）简单选择排序法 （B B）堆排序法）堆排序法首先将第一个记录的关键字和第二个记录的关键字进行比较，首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直至第个记录的关键字。依此类推，直至第n-1n-1个记录和第个记录和第n n个记录个记录的关键字进行过比较为止。完成第一趟冒泡排序，其结果使的关键字进行过比较为止。完成第一趟冒泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上，然后得关键字最大的记录被安置到最后一个记录的位置上，然后进行第二趟冒泡排序，进行第二趟冒泡排序，直至排序结束。，直至排序结束。 冒泡排序每一遍的从前到后扫描都把排序范围内的最大冒泡排序每一遍的从前到后扫描都把排序范围内的最大元素沉到了表的底部，每一遍的从后往前扫描，都把排序范元素沉到了表的底部，每一遍的从后往前扫描，都把排序范围内的最小元素像气泡一样浮到了表的最前面。围内的最小元素像气泡一样浮到了表的最前面。 在最坏的情况下，对长度为在最坏的情况下，对长度为n n的线性表排序，冒泡排序需要的线性表排序，冒泡排序需要比较的次数为比较的次数为n(n-1)/2n(n-1)