等级考基础数据结构

1、等级考基础数据结构第1页，共113页，2022年，5月20日，5点44分，星期二1.1 数据结构的研究对象数据结构的研究内容： 非数值数据之间的结构关系，及如何表示，如何存储，如何处理。归纳为三部分：逻辑结构、存储结构和运算集合。 按某种逻辑关系把一批数据组织起来，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义一个运算的集合。第2页，共113页，2022年，5月20日，5点44分，星期二 逻辑结构是数据结构的抽象，存储结构是数据结构的实现存储结构的二种类型: 顺序存储结构通过在存储器中的相对位置， 表示数据的逻辑结构。 非顺序存储结构（链式存储结构） -由指针表示数据间的逻辑关

2、系。第3页，共113页，2022年，5月20日，5点44分，星期二第4页，共113页，2022年，5月20日，5点44分，星期二1.3 常用的数据结构 (1) 线性结构：结构中的数据元素之间存在着一对一的线性关系。线性表、栈、队、字符串、数组 (2) 树形结构：结构中的数据元素之间存在着一对多的层次关系。-非线性结构 (3) 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。- 非线性结构第5页，共113页，2022年，5月20日，5点44分，星期二14 算法与算法分析 1.4 算法与算法分析一 算法的概念 算法是对特定问题求解步骤的一种描述 算法的基本特征：1）可行性：组成算法

3、的操作必须能够在计算机上实现。2）确定性：算法的每一步操作必须清晰无二义性。3）有穷性：算法必须在有限步内结束；4）有足够的情报：0个或多个输入；1个或多个输出； 算法描述的方法很多，如自然语言、框图、类C等例: 求两个正整数 m，n 中的最大数MAX的算法 （1）若 m n 则 max=m （2）若 m = n 则 max=n 第6页，共113页，2022年，5月20日，5点44分，星期二1、正确性： (1) 没有语法错误； (2) 对于几组输入数据能够得出满足要求的结果； (3) 对于精心选择的典型而苛刻的几组输入数据能够得到满足要求的结果。 (4) 对于一切合法的输入数据都能产生满足要求

4、的结果。 2、可读性：便于阅读、理解、调试、修改；3、健壮性：对不合法的输入能作出正确的反映与处理；4、高效性：执行时间短（时间复杂度）、 需求存储空间省（空间复杂度）评价算法标准第7页，共113页，2022年，5月20日，5点44分，星期二1 时间复杂度T（n） 以求解问题的基本操作的执行次数作为算法时间的度量。 14 算法与算法分析O（n3） 称为矩阵相乘算法时间复杂度；O（n3）表示矩阵相乘算法执行时间与n3成正比, 即O（n3）与n3 同一数量级； 例 n 阶矩 阵相乘的算法For ( i = 1; i=n; i+ ) For (j = 1; j=n; j+ ) c i j = 0 ;

5、 For (k = 1; k= n; k+ ) c i j += a i k * b k j 乘法 加法执行次数均为 n3 矩阵相乘的基本运算：乘法 加法；第8页，共113页，2022年，5月20日，5点44分，星期二数据结构中常用的时间复杂度频率计数有7个： O(1) 常数型 O(n)线性型 O(n2)平方型 O(n3)立方型 O(2n)指数型 O(log2n)对数型 O(nlog2n)二维型第9页，共113页，2022年，5月20日，5点44分，星期二 14 算法与算法分析2 算法空间复杂度 用执行算法所需的辅助空间的大小作为算法所需空间的度量。 设执行算法所需的辅助空间是问题规模n的某个

6、函数g(n),则算法空间复杂度记作： S（n）= O(g(n)表示算法辅助空间的增长率与g(n) 的增长率相同例计算 解法1 先计算x 的幂, 存于power 中,再分别乘以相应的系数 # define N 100 float evaluate (float coef , float x , int n ) float powerN, f; int i; for (power 0=1, i = 1; i=n; i+ ) poweri=x*poweri-1; for (f = 0, i=0; ideta=a; q-next=p- next; p- next =q;headzyxpyxzphead

7、a q第24页，共113页，2022年，5月20日，5点44分，星期二插入操作功能：在线性链表的第i个元素结点之前插入一个新元素结点e； 插入操作图示：2. 3. 1 线性链表插入前插入后 ai-1aia2a1ai+1nanheadai-1aia2a1ai+1nanehead第25页，共113页，2022年，5月20日，5点44分，星期二 4）删除结点q=p-next; p- next =q- next; free(q);headzyxqyxzqheadpp第26页，共113页，2022年，5月20日，5点44分，星期二 2. 3. 1 线性链表删除前删除后ai-1aia2a1ai+1nanh

8、eadai-1aia2a1ai+1nanheadppqq第27页，共113页，2022年，5月20日，5点44分，星期二2. 3. 1 线性链表小结线性链表是线性表的一种链式存储结构 线性链表的特点 1 通过保存直接后继元素的存储位置来表示 数据元素之间的逻辑关系； 2 插入、删除操作通过修改结点的指针实现； 3 不能随机存取元素；第28页，共113页，2022年，5月20日，5点44分，星期二1 循环链表的概念 循环链表的特点是将线性链表的最后一个结点的指针指向链表的第一个结点（首尾相连的单链表）2 循环链表图示2. 3 . 2 循环链表(a)非空表 （b）空表headheada1an第29

9、页，共113页，2022年，5月20日，5点44分，星期二循环链表说明在解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面； 对循环链表，有时不给出头指针，而是给出尾指针aa1ana-next给出尾指针的循环链表第30页，共113页，2022年，5月20日，5点44分，星期二2.3.4 双向链表 循环单链表，虽然从任一结点出发沿着指针链能找到其前件，但时间耗费是O(n) 。如果希望从表中快速确定某一个结点的前件，另一个解决方法是在链表的每个结点里再增加一个指向其前件的指针域prior。 这样形成的链表中就有两条方向不同的链，称为双向链表。第31页，共113页，2

10、022年，5月20日，5点44分，星期二B例:线性表的顺序存储结构和线性表的链式存储结构分别是?A) 顺序存取的存储结构、顺序存取的存储结构B) 随机存取的存储结构、顺序存取的存储结构C) 随机存取的存储结构、随机存取的存储结构D) 任意存取的存储结构、任意存取的存储结构第32页，共113页，2022年，5月20日，5点44分，星期二例:链表不具有的特点是A) 不必事先估计存储空间B) 可随机访问任一元素C) 插入删除不需要移动元素D) 所需空间与线性表长度成正比 B第33页，共113页，2022年，5月20日，5点44分，星期二例:数据结构分为逻辑结构和存储结构，循环队列属于【5】结构。存储

11、结构第34页，共113页，2022年，5月20日，5点44分，星期二在单链表中，增加头结点的目的是A) 方便运算的实现B) 使单链表至少有一个结点C) 标识表结点中首结点的位置 D) 说明单链表是线性表的链式存储实现 A第35页，共113页，2022年，5月20日，5点44分，星期二线性表小结 线性表的顺序存储结构顺序表， 链式存储结构-线性链表,循环链表, 双向链表.不同的存储结构，线性表的同一操作的算法是不同的:在顺序存储结构下，线性表的插入、删除操作，通过移动元素实现;在线性链表存储结构下，线性表的插入、删除操作，通过修改指针实现。第36页，共113页，2022年，5月20日，5点44分

12、，星期二3.1 栈栈是限定仅能在表尾一端进行插入、删除操作的线性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入删除3.1.1 栈的概念一 什么是栈?第37页，共113页，2022年，5月20日，5点44分，星期二3.1 栈 将表中允许进行插入、删除操作的一端称为栈顶(Top)，栈顶的当前位置是动态变化的，由一个栈顶指针指示其位置。表的另一端称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作称为进栈或入栈，删除操作称为出栈或退栈。 第38页，共113页，2022年，5月20日，5点44分，星期二栈 第39页，共113页，2022年，5月20日，5点

13、44分，星期二3.1 栈栈的示意图出栈进栈栈的特点后进先出第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素栈顶栈底ana2a1第40页，共113页，2022年，5月20日，5点44分，星期二B例:如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是? A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2D) 任意顺序 第41页，共113页，2022年，5月20日，5点44分，星期二例:栈和队列的共同特点是A) 都是先进先出B) 都是先进后出C) 只允许在端点处插入和删除元素D) 没有共同点 C 第

14、42页，共113页，2022年，5月20日，5点44分，星期二例:下列关于栈的描述中错误的是A)栈是先进后出的线性表B) 栈只能顺序存储C) 栈具有记忆作用D) 对栈的插入与删除操作中，不需要改变栈底指针B第43页，共113页，2022年，5月20日，5点44分，星期二 小 结 1 栈是限定仅能在表尾一端进行插入、 删除操作的线性表； 2 栈的元素具有后进先出的特点； 3 栈顶元素的位置由一个称为栈顶指针的 变量指示， 进栈、出栈操作要修改栈顶指针； 3.1 栈第44页，共113页，2022年，5月20日，5点44分，星期二32 队列3.2.1 队列的概念一 什么是队列队列是限定仅能在表头进行

15、删除，表尾进行插入的线性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入删除第45页，共113页，2022年，5月20日，5点44分，星期二33 队列 a1 a2 a3 an入队列队头队尾出队列队 列 的 示 意 图队列的特点先进先出第一个入队的元素在队头，最后一个入队的元素在队尾，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素第46页，共113页，2022年，5月20日，5点44分，星期二rearfrontJ1rearfrontJ2（a)空队列(b)J1,J2相继入队列(c)J1出队(d)J3,J4, J5和J6相继入队之后,J2出队rearfron

16、t0123453. 3 队列rearfrontJ5J4J3front,rear为整数 又有J7入队, 怎么办？J2J6第47页，共113页，2022年，5月20日，5点44分，星期二3. 3 队列3 . 循环队列frontrearJ6J4J53 124 05rear54 03 12frontJ6J7J8J9J4J5frontrear54 03 12(b)队空(a)队满J7rear第48页，共113页，2022年，5月20日，5点44分，星期二3. 3 队列判分队空、队满方法：1）另设一个标志S以区分队空、队满。2）S=0 队空： front=rear; S=1 队满： front=rear;f

17、ront54 03 12J6J7J8J4J5（c）rear第49页，共113页，2022年，5月20日，5点44分，星期二3. 3 队列入队操作 ：将元素 x 插入队尾 frontrear54 03 12J1J3J2xfrontrear54 03 12J1J3J2元素 x 入队前元素 x 入队后第50页，共113页，2022年，5月20日，5点44分，星期二3. 3 队列出队操作 ：删除队头元素； frontrear54 03 12J1J3J2出队操作前frontrear54 03 12J1J3J2出队操作后第51页，共113页，2022年，5月20日，5点44分，星期二 小 结 1 队列是限

18、定仅能在表尾一端进行插入，表头一端删除 操作的线性表； 2 队列中的元素具有先进先出的特点； 3 队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示， 4 入队操作要修改队尾指针，出队操作要修改队头指针； 第52页，共113页，2022年，5月20日，5点44分，星期二树和二叉树 第53页，共113页，2022年，5月20日，5点44分，星期二1树的定义 树是n个结点的有限集合T，当n=0时，称为空树；当n0时，T满足如下条件：在任一棵非空树中：（1）有且仅有一个称为根的结点。（2）其余结点可分为M个互不相交的子集合，而且这些子集中的每一个本身又是一棵树，也称为根的子树。JIACBDH

19、GFEKLM第54页，共113页，2022年，5月20日，5点44分，星期二2树的实例树可表示具有分枝结构关系的对象例1家族族谱 设某家庭有13个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可用树表示：JIACBDHGFEKLM第55页，共113页，2022年，5月20日，5点44分，星期二计算机中树是常用的数据组织形式 尽管有些应用中数据元素之间并不存在分支结构关系，但为了便于管理和使用数据，将它们用树的形式来组织。例2 计算机的文件系统 不论是DOS文件系统还是window文件系统，所有的文件都是用树的形式来组织的。文件夹1 文件夹n 文件1 文件2文件夹11 文

20、件夹12 文件11 文件12C盘第56页，共113页，2022年，5月20日，5点44分，星期二3、树的 基本术语 树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子， B、C是A的孩子；双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；兄弟结点：同一双亲的孩子结点， H、I、 J互为兄弟；堂兄结点：同一层上结点， E、F、G、H、I、J、互为堂兄弟；JIACBDHGFEKLM第57页，共113页，2022年，5月20日，5点44分，星期二3、树的 基本术语结点的层次：根结点的层次定义为1；根的孩子为第二层，依此类推；树的深度：树中所有结点的层

21、次的最大值结点的度：结点子树的个数树的度： 树中结点度的最大值。叶子结点：度为 0 的结点；分枝结点：度不为0的结点；JIACBDHGFEKLM第58页，共113页，2022年，5月20日，5点44分，星期二一 二叉树的概念1 二叉树的定义二叉树： 或为空树，或由根及两颗互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。 A F G E D C B第59页，共113页，2022年，5月20日，5点44分，星期二一 二叉树的概念二叉树说明1）二叉树中每个结点最多有两个子树；既：二叉树每个结点度小于等于2;2）左、右子树不能颠倒有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树

22、的概念;第60页，共113页，2022年，5月20日，5点44分，星期二 (a)、(b)是不同的二叉树， (a)的左子树有四个结点，(b)的左子树有两个结点(a)(b) G E D C B A F G E D C B FA第61页，共113页，2022年，5月20日，5点44分，星期二 2 二叉树的基本形态(a)空树(b)只有根(c) 右子树空(e) 左子树空(d) 左、右子树非空第62页，共113页，2022年，5月20日，5点44分，星期二二、 二叉树的性质 性质1: 在二叉树的第i层上至多有2i-1个结点(i1)。 性质2: 深度为k的二叉树至多有2k-1个结点（k1）。 第63页，共1

23、13页，2022年，5月20日，5点44分，星期二 性质3: 对任意一棵二叉树T，若叶结点数为n0，而其度为2的结点数为n2，则n0=n2+1。第64页，共113页，2022年，5月20日，5点44分，星期二两种特殊的二叉树满二叉树：深度为k的二叉树，如有2k-1个结点则称为满二叉树； A G F E D C B A C BK=3的满二叉树K=2的满二叉树第65页，共113页，2022年，5月20日，5点44分，星期二满二叉树的顺序表示： 从二叉树的根开始， 从上到下， 从左到右，逐层进行编号（1， 2， ， n）。例如图（a）所示的满二叉树的顺序表示为:(1， 2， 3， 4， 5， 6，

24、7， 8， 9， 10， 11， 12， 13， 14， 15)。 第66页，共113页，2022年，5月20日，5点44分，星期二 完全二叉树： 深度为k，结点数为n的二叉树，如果其结点1n的位置序号分别与满二叉树的结点1n的位置序号一一对应，则为完全二叉树， 如上图 (b)所示。 满二叉树必为完全二叉树， 而完全二叉树不一定是满二叉树。 第67页，共113页，2022年，5月20日，5点44分，星期二 性质4：具有n个结点的完全二叉树的深度为log2n+1。 第68页，共113页，2022年，5月20日，5点44分，星期二 性质5: 对于有n个结点的完全二叉树， 按照从上到下、从左到右的顺

25、序对二叉树中的所有结点从1开始顺序编号， 则对于任意的序号为i的结点有： （1） 如i=1，则序号为i的结点是根结点， 无双亲结点； 如i1， 则序号为i的结点的双亲结点序号为i/2 （下取整） （2） 如2in，则序号为i的结点无左孩子；如2in，则序号为i的结点的左孩子结点的序号为2i。 （3） 如2i1n，则序号为i的结点无右孩子；如2i1n， 则序号为i的结点的右孩子结点的序号为2i1。 第69页，共113页，2022年，5月20日，5点44分，星期二 二叉树存储结构-二叉链表 二叉链表中每个结点包含三个域：数据域、左指针域、右指针域 A F E D C B二叉链表图示 D A B C

26、 E F 第70页，共113页，2022年，5月20日，5点44分，星期二 若一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域， 其中必有n+1个空的指针域。 第71页，共113页，2022年，5月20日，5点44分，星期二二、二叉树的遍历遍历：按某种顺序访问二叉树的每个结点，而且每个结点仅被访问一次。访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。 如何访问二叉树的每个结点， 而且每个结点仅被访问一次？第72页，共113页，2022年，5月20日，5点44分，星期二二叉树的遍历方法 二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子

27、树和遍历右子树令：L：遍历左子树 T：访问根结点 R：遍历右子树 约定先左后右,有三种遍历方法： T L R前序遍历、 L T R中序遍历、 L R T后序遍历。 A F G E D C B第73页，共113页，2022年，5月20日，5点44分，星期二 先序遍历（T L R） 若二叉树非空 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树； 先序遍历序列：A,B,D,E,G,C,F例：先序遍历右图所示的二叉树 （1）访问根结点A （2）先序遍历左子树：即按 T L R 的顺序遍历左子树 （3）先序遍历右子树：即按 T L R 的顺序遍历右子树 A F G E D C B第74

28、页，共113页，2022年，5月20日，5点44分，星期二中序遍历（L T R）若二叉树非空（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树 中序遍历序列： D,B,G,E,A,C,F例：中序遍历右图所示的二叉树 （1）中序遍历左子树：即按 L T R 的顺序遍历左子树 （2）访问根结点A （3）中序遍历右子树：即按 L T R 的顺序遍历右子树 A F G E D C B第75页，共113页，2022年，5月20日，5点44分，星期二后序遍历（L R T）若二叉树非空（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点 后序遍历序列： D,G,E,B,F,C,A例：后序遍历右图所

29、示的二叉树 （1）后序遍历左子树：即按 L R T 的顺序遍历左子树 （2）后序遍历右子树：即按 L R T 的顺序遍历右子树 （3）访问根结点A A F G E D C B第76页，共113页，2022年，5月20日，5点44分，星期二 后序遍历序列：a,b,c,d,-,*,+,e,f,/,-中序遍历序列：a,+,b,*,c,-,d,-,e,/,f 例：中序遍历、后序遍历下图所示的二叉树 e d c b f a + * / - -第77页，共113页，2022年，5月20日，5点44分，星期二例:已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为

30、? A) GEDHFBCAB) DGEBHFCAC) ABCDEFGHD) ACBFEDHG B第78页，共113页，2022年，5月20日，5点44分，星期二例:已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是A) acbedB) decab C) deabcD) cedba D第79页，共113页，2022年，5月20日，5点44分，星期二二叉树1 二叉树： 或为空树，或由根及两颗互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树； 2 二叉树可以用链式结构存储；遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。 二叉树的遍历可以分解为

31、：访问根，遍历左子树和遍历右子树，常用的三种遍历算法：先序遍历、中序遍历、后序遍历；第80页，共113页，2022年，5月20日，5点44分，星期二查找 第81页，共113页，2022年，5月20日，5点44分，星期二5.1 查找的基本概念 查找（列）表：由同一类型的数据元素（或记录）构成的集合， 可利用任意数据结构实现。 关键字：数据元素的某个（几个）数据项的值。如果一个数据项可以唯一标识列表中的一个数据元素， 则称其为关键字。第82页，共113页，2022年，5月20日，5点44分，星期二 查找： 根据给定的关键字值，在特定的查找（列）表中确定一个其关键字与给定值相同的数据元素，并返回该数

32、据元素在列表中的位置。若找到相应的数据元素， 称查找成功，否则称查找失败 第83页，共113页，2022年，5月20日，5点44分，星期二52 线性表的查找5.2.1 顺序查找-最简单的查找方法顺序查找的基本思想 从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于的元素，则查找失败。 顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。第84页，共113页，2022年，5月20日，5点44分，星期二顺序查找

33、算法的性能。假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n， 则顺序查找算法的平均查找长度为： 第85页，共113页，2022年，5月20日，5点44分，星期二顺序查找的特点 顺序查找的优点是算法简单，对查找表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序或无序排，它都同样适用。顺序查找的缺点是查找效率低，当 n 较大时，不宜采用顺序查找。 第86页，共113页，2022年，5月20日，5点44分，星期二二分查找（折半查找）1.二分查找的基本思想高效率的查找方法。要求表中元

34、素按关键字有序(升序或降序)。假设表中元素为升序排列。二分查找的基本思想是：首先将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表， 如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。第87页，共113页，2022年，5月20日，5点44分，星期二例如，假设给定有序表中关键字为：05,13,19,21,37,56,64,74,80,88,92，查找K=21的情况： 0 1 2 3 4 5 6 7 8 9 10 0

35、 1 2 3 4 5 6 7 8 9 10第88页，共113页，2022年，5月20日，5点44分，星期二 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10第89页，共113页，2022年，5月20日，5点44分，星期二3.二分查找的性能分析 二分查找的过程可以用二叉树来描述。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为二分查找的判定树。例如，给定的关键字序列05,13,19,21,37,56,64,74,80,88,92，的判定树。 0 1 2 3 4 5 6 7

36、 8 9 10第90页，共113页，2022年，5月20日，5点44分，星期二在长度为n的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为 log2n例:对于长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为?A) log2n B) n/2 C) n D) n+1C第91页，共113页，2022年，5月20日，5点44分，星期二 排序 第92页，共113页，2022年，5月20日，5点44分，星期二61 基本概念 6.1.1 排序定义 排序就是把一组记录（元素）按照某个域的值的递增或递减的次序重新排列的过程。(按学号的递增)表7-1 学生档案表学号姓名年龄性别99001王晓佳

37、18男99002林一鹏19男99003谢宁17女99004张丽娟18女99005周涛20男99006李小燕16女第93页，共113页，2022年，5月20日，5点44分，星期二为讨论方便，我们直接将排序码写成一个一维数组的形式，并且在没有声明的情形下，所有排序都按排序码的值递增排列。 排序 插入排序（直插排序、二分排序、希尔排序） 交换排序（冒泡排序、快速排序） 选择排序 （直选排序、堆排序） 归并排序（二路归并排序、多路归并排序） 第94页，共113页，2022年，5月20日，5点44分，星期二 62 插入排序 直接插入排序1直接插入排序（Straight Insertion Sorting

38、）基本思想：把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。第95页，共113页，2022年，5月20日，5点44分，星期二例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。它的直接插入排序的执行过程如图7-1所示。第96页，共113页，2022年，5月20日，5点44分，星期二3直接插入排序的效率分析直接插入排序算法十分简单。空间:只需要一个元素的辅助空间，用于元素的位置交换。时间

39、:外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次；最多比较i次，移动i2次（逆序）（i=1，2，n-1）。直接插入排序的时间复杂度为O（n2）。最坏情况比较n(n-1)/2第97页，共113页，2022年，5月20日，5点44分，星期二希尔排序希尔排序(缩小增量排序):1959年由提出来的。基本思想：先将整个待排元素序列分割成若干个子序列（由 “增量”确定）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。第98页，共113页，2022年，5月20日，5点

40、44分，星期二例如，n=8，数组array 的八个元素分别为：91，67，35，62，29，72，46，57。下面用图7-2给出希尔排序算法的执行过程。第99页，共113页，2022年，5月20日，5点44分，星期二希尔排序的效率分析与增量有关，最坏情况，希尔排序的时间复杂性在O（nlog2n）。第100页，共113页，2022年，5月20日，5点44分，星期二63 交换排序6.3.1 冒泡排序基本思想:对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部，就象水底下的气泡一样逐渐向上冒。第101页，共113页，2022

41、年，5月20日，5点44分，星期二例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。下面用图7-3给出冒泡排序算法的执行过程。第102页，共113页，2022年，5月20日，5点44分，星期二 冒泡排序的效率分析若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(n2-n)/2，移动次数为3(n2-n )/2，最坏情况比较n(n-1)/2因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。第103页，共113页，2022年，5月20日，5点

42、44分，星期二6.3.2 快速排序基本思想是：取待排序序列中的某个元素（一般第一个元素）作为基准，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行快速排序，直至整个序列有序。元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面，排序码较小的记录一次就能够交换到前面，记录每次移动的距离较远，因而总的比较和移动次数较少。 第104页，共113页，2022年，5月20日，5点44分，星期二例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图7-4所示。第105页，共113页，2022年，5月20日，5点44分，星期二3快速排序的效率分析