第一章数据结构课件

全国计算机等级考试全国计算机等级考试公共基础知识公共基础知识 全国计算机等级考试二级VFP语言试卷笔试满分100分，其中含公共基础知识部分的30分。共有两种题型：选择70分30小题，填空30分15小题全国计算机等级考试二级VFP语言上机满分为100分，共有三种类型考题。1、基本操作题（30分）2、简单应用题（40分）3、综合应用题（30分）基本数据结构和算法 第一章第一章描述描述算法算法设给定两个正整数设给定两个正整数m=112和和n=64，利用，利用辗转相除法求它们的辗转相除法求它们的最大公约数。最大公约数。（1）112除以除以64，余数为，余数为48；（2）64除以除以48，余数为，余数为16；（3）48除以除以16，余数为，余数为0；答答:112和和64的的最最大大公公约约数数为为16。引入算法引入算法算法的五个重要算法的五个重要特性特性算法：算法：解题方案的准确而完整的描述解题方案的准确而完整的描述解题方案的准确而完整的描述解题方案的准确而完整的描述 基本特征基本特征（1）有有穷穷性性：算算法法必必须须在在执执行行有有穷穷步步之之后后结结束束，每每一一步都可在有穷时间内完成。步都可在有穷时间内完成。（2）确定性：确定性：对相同的输入只能得出相同的输出。对相同的输入只能得出相同的输出。（3）可行性：可行性：算法所描述的操作都是可实现的。算法所描述的操作都是可实现的。（4）拥有足够的情报。拥有足够的情报。算法设计的要求算法设计的要求 （1）正确性：正确性：算法应当满足具体问题的需求；算法应当满足具体问题的需求；（2）可可读读性性：可可读读性性好好的的算算法法有有助助人人们们于于对对算算法的理解；法的理解；（3）健健壮壮性性：当当输输入入非非法法数数据据时时，算算法法也也能能适适当当地地做做出出反反应应或或进进行行处处理理，而而不不会会产产生生莫莫名名其其妙的输出结果；妙的输出结果；（4）效效率率与与低低存存贮贮量量：效效率率指指的的是是算算法法执执行行的的时时间间，解解决决同同一一问问题题，执执行行时时间间短短的的算算法法效效率率高高。存存储储量量指指算算法法执执行行过过程程中中所所需需要要的的最最大大存存储空间。储空间。算法基本要素算法基本要素一个算法通常由两个基本要素所组成：一个算法通常由两个基本要素所组成：1.对数据对象的运算和操作对数据对象的运算和操作2.算法的控制结构算法的控制结构基本运算和操作分为四类：基本运算和操作分为四类：1.算术运算算术运算 2.逻辑运算逻辑运算 3.关系运算关系运算 4.数据传输数据传输算法的控制结构：算法的控制结构：顺序顺序 选择选择 循环循环 算法优劣分析算法优劣分析 同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度时间复杂度和空间复杂度空间复杂度来考虑。时间复杂度 是指执行算法所需要的计算工作量，是由算法执行的基本运算次数来度量。空间复杂度是指算法在计算机内执行时所需的内存空间。数据结构数据结构现实中对象之间的关系线性关系：如列车中各车箱之间的关系、排队买车票人线性关系：如列车中各车箱之间的关系、排队买车票人之间的关系、一叠盘子中各盘子之间的关系等。之间的关系、一叠盘子中各盘子之间的关系等。层次关系：如学校的组织结构、人的辈分关系等。层次关系：如学校的组织结构、人的辈分关系等。网状关系：如城市铁路交通网、电话网、计算机网络等。网状关系：如城市铁路交通网、电话网、计算机网络等。应用举例1学籍档案管理假设一个学籍档案管理系统应包含如下表1-1所示的学生信息。特点：l每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；l表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；l对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。数据结构主要研究以下三个方面的问题：数据结构主要研究以下三个方面的问题：数据的逻辑结构数据的存储结构对各种数据结构进行的运算 注意：注意：讨论以上问题讨论以上问题主要目的主要目的是为了是为了提高数据处理的提高数据处理的效率效率，提高效率包括两个方面：，提高效率包括两个方面：一是提高数据处理的速度一是提高数据处理的速度二是节省在数据处理过程中所占用的计算机二是节省在数据处理过程中所占用的计算机存储空间存储空间 数据结构概论数据结构概论数数据据：能能输输入入到到计计算算机机中中并并被被计计算算机机存存储储、加加工工的的符符号号的的总总称称。（数数值值型型、布布尔尔型型、字字符串、表格、语音、图片、图像等）符串、表格、语音、图片、图像等）数数据据元元素素：数数据据的的基基本本单单位位（结结点点、顶顶点点或或记录）记录）通常作为一个整体进行处理。通常作为一个整体进行处理。数据项：数据项：数据的不可分割的数据的不可分割的最小最小单位。单位。一个数据元素可以由若干个数据项构成。一个数据元素可以由若干个数据项构成。逻辑结构逻辑结构1.数据的逻辑结构分为线性结构和非线性结构两大类。数据的逻辑结构分为线性结构和非线性结构两大类。(1)线性结构线性结构:包括数组、链表、包括数组、链表、栈、队列、优先级队列等栈、队列、优先级队列等;线性结构的基本特征线性结构的基本特征存在唯一的存在唯一的“第一个第一个”数据元素；数据元素；存在唯一的存在唯一的“最后一个最后一个”数据元素；数据元素；除第一个外，每个数据元素均有且只有一个除第一个外，每个数据元素均有且只有一个直接前驱直接前驱元素；元素；除最后一个外，每个数据元素均有且只有一个除最后一个外，每个数据元素均有且只有一个直接后继直接后继元素。元素。(2)非线性结构非线性结构:包括树、图等包括树、图等.答：指数据元素之间的逻辑关系。即从逻辑关系上描述答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。数据，它与数据的存储无关，是独立于计算机的。何为数据的逻辑结构？何为数据的逻辑结构？存存 储储 结结 构构存储结构概念：数据的逻辑结构在计算机存储空间中的存放存储结构概念：数据的逻辑结构在计算机存储空间中的存放形式形式常见存储结构：常见存储结构：(1)顺序存储结构：顺序存储结构：特点是借助于数据元素的相对存储位特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构置来表示数据元素之间的逻辑结构.即逻辑上相邻即逻辑上相邻,物理上也相邻物理上也相邻.(2)链式存储结构：链式存储结构：特点是借助于指示数据元素地址的指特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。针表示数据元素之间的逻辑结构。(3)索引存储结构索引存储结构:线性表线性表的概念线性表的概念 线性表：线性表：是线性结构的一种具体表现，所含结是线性结构的一种具体表现，所含结点的个数称为表长，表长为点的个数称为表长，表长为0的线性表称为的线性表称为空表。空表。春春夏夏秋秋冬冬线线性性表表（a1,a2,ai,ai+1,an）的的顺顺序序表表示示：用用一一组组地地址址连连续续的的存存贮贮单单元元依次存贮依次存贮线性表的数据元素。线性表的数据元素。顺顺序序表表的的特特点点：逻逻辑辑结结构构中中相相邻邻的的结结点点在在存储结构中仍相邻存储结构中仍相邻。顺顺序序表表的的容容量量（maxsize）：线线性性表表实实际际达到的最大长度。达到的最大长度。表长表长：当前表的长度，小于等于表的容量。：当前表的长度，小于等于表的容量。线性表的顺序存储结构线性表的顺序表示（图示）线性表的顺序表示（图示）b数据元素数据元素a1的存储地址的存储地址l每个数据元素所需的存储单元大小每个数据元素所需的存储单元大小存储地址存储地址内存状态内存状态位序位序ba1 1b+la2 2b+(i-1)lai Ib+(n-1)lan n插插入入运运算算：在在表表的的第第i(1=i=n+1)个个位位置置上上，插插入入一一个个新新结结点点x，使使长长度度为为n的的线线性性表变成长度为表变成长度为n+1的线性表的线性表插入算法的基本插入算法的基本步骤步骤：将结点将结点ai,an各各后移后移一位；一位；将新结点将新结点x置入第置入第i个位置；个位置；表长加表长加1插入一个元素所需平均插入一个元素所需平均移动次数：移动次数：n/2线性表的插入运算在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：12132124283042771213212425252830427712345678123456789插入插入25252525删删除除运运算算：将将表表的的第第i(1=inext是是否否为为空空，而而是是它它们们是是否等于头指针。否等于头指针。循环链表循环链表H(a)a)空表空表a1a2a3Haian(b)b)非空表非空表双向链表双向链表双双向向链链表表的的特特点点表表中中的的每每个个结结点点有有两两个个指指针针域域，一一个个指指向向后后继继结结点点，一一个个指指向向前趋结点，前趋结点，整个链表形成两个环。整个链表形成两个环。从从表表的的任任意意结结点点出出发发可可以以通通过过正正向向环环（或或反向环）找到表中其它结点。反向环）找到表中其它结点。priordatanext结点：结点：L(a)a)空表空表(b)b)非空表非空表LA AB BC C35栈和队列36“取”操作必须在这端进行“放”操作必须在同一端进行栈栈栈（栈（stack）:先进后出先进后出(FILO）的线性表。的线性表。或或后进先出（后进先出（LIFO）的线性表。的线性表。或仅在或仅在表尾表尾进行进行插入插入和和删除删除操作的线性表。操作的线性表。栈顶（栈顶（top）:线性表的线性表的表尾端表尾端，即可操作端。，即可操作端。栈底（栈底（bottom）:线性表的线性表的表头表头。栈底栈底栈顶栈顶.a1a2a3an-1an入栈入栈(push)出栈出栈(pop)栈的基本操作进栈操作进栈操作 ：将数据元素将数据元素x x插入栈插入栈S S，使，使x x成为成为S S的栈顶元素；的栈顶元素；出栈操作：出栈操作：当栈不空时返回栈顶元素为该函数的值，然后删除栈顶当栈不空时返回栈顶元素为该函数的值，然后删除栈顶元素；元素；取栈顶元素取栈顶元素 ：当栈不空时返回栈顶元素为该函数的值，但栈顶保持不当栈不空时返回栈顶元素为该函数的值，但栈顶保持不变；变；队列 排队只能排在尾部,排在对头的先得到服务;“插队”是不允许的.换言之,插入和删除只能在线性表的两头分别进行;插入的一端称为队尾,删除的一端称为队头;其特点是:先进先出(FIFO)队列(Queues)是生活中“排队”的抽象队列队列（Queue）:先进先出先进先出(First In First Out)(缩写为缩写为FIFO）的线性表。的线性表。仅在仅在队尾队尾进行进行插入插入和和队头队头进行进行删除删除操作的线操作的线性表。性表。队头队头（front）:线性表的表头端，即线性表的表头端，即可删除端可删除端。队尾队尾（rear）:线性表的表尾端，即线性表的表尾端，即可插入端可插入端。队头队头队尾队尾.a1a2a3an-1an入队列入队列(Enqueue)出队列出队列(Dequeque)循环队列（队列的顺序表示与实现）采用顺序存储结构采用顺序存储结构约定约定:1)初始空队列：初始空队列：front=rear=0;2)循环队列中元素个数循环队列中元素个数=rear-front rear front102354空队列空队列空队列空队列J1J2J3 front rearJ1J1、J2J2和和和和J3J3相继入列相继入列相继入列相继入列J3 front rearJ1J1、J2J2相继被删除相继被删除相继被删除相继被删除J5J6 front rearJ4J4、J5J5和和和和J6J6相继相继相继相继入列后入列后入列后入列后J3J3、J4J4被删被删被删被删除除除除树和二叉树树和二叉树特点：特点：特点：特点：非线性结构，一个直接前驱，但可能有多个非线性结构，一个直接前驱，但可能有多个非线性结构，一个直接前驱，但可能有多个非线性结构，一个直接前驱，但可能有多个直接后继（直接后继（直接后继（直接后继（1 1 1 1：n n n n）一对多一对多社会的组织结构社会的组织结构家族的族谱家族的族谱计算机中目录组织计算机中目录组织树的类型定义树的类型定义 树是一类重要的非线性数据结构，是以分支关系定义的层次结构。即树的数据元素即树的数据元素一个结点所拥有的后件一个结点所拥有的后件的个数的个数结点结点结点的度结点的度 根根 叶子叶子树的度树的度树的深度树的深度(或高度或高度)即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)所有结点度中的最大值（所有结点度中的最大值（Max各结点的度各结点的度）指所有结点中最大的层数（指所有结点中最大的层数（Max各结点的层次各结点的层次）问：问：右上图中的结点数右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4（有几个直接后继就是几度）（有几个直接后继就是几度）ABCGEIDHFJFLK二叉树二叉树的五种基本形态：二叉树的五种基本形态：(c)右子树为空的右子树为空的二叉树二叉树(d)左、右子树均为非空的左、右子树均为非空的二叉树二叉树(e)左左子树为空子树为空的二叉树的二叉树(a)A(b)A(c)A(d)A(e)(a)空二叉树空二叉树(b)仅有根结点的二叉树仅有根结点的二叉树逻辑结构：逻辑结构：一对二（一对二（1:2）基本特征基本特征:每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2 2的结点）；的结点）；左子树和右子树次序不能颠倒。左子树和右子树次序不能颠倒。二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。树的、互不交的二叉树组成。两种特殊的二叉树两种特殊的二叉树1.1.满二叉树：满二叉树：一颗树中所有叶结点均在同一阶一颗树中所有叶结点均在同一阶层，而其它非终端结点的分支度均为层，而其它非终端结点的分支度均为2 2，则此，则此树为一颗满二叉树。树为一颗满二叉树。若该树的高度为若该树的高度为h h，则此满二叉树的结点为，则此满二叉树的结点为2 2h-1h-1。2.完全二叉树：完全二叉树：如果一颗二叉树只有最下一层如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树；中在该层的最左端，则称为完全二叉树；二叉树的性质（重要）性质性质1 1 在二叉树的第在二叉树的第i i层上层上最多有最多有2 2i-1i-1个结点个结点性质性质2 2 深度为深度为k k的二叉树最的二叉树最多有多有2 2k k-1-1个结点个结点性质性质3 3 设二叉树叶子结点设二叉树叶子结点数为数为n n0 0，度为度为2 2的结点的结点n n2 2，则则n n0 0=n n2 2+1+1层次层次1234ABCDEFGH对完全二叉树的结点编号：对完全二叉树的结点编号：从上到下，从左到右从上到下，从左到右 A A F F E E D D C C B B1 12 23 34 45 56 6性质性质4 4 具有具有n n个结点的完全二叉树的深度为：个结点的完全二叉树的深度为：loglog2 2 n +1n +1性质性质5 5：在完全二叉树中编号为在完全二叉树中编号为i i的结点的结点1 1）若有左孩子，则左孩编号为）若有左孩子，则左孩编号为2 2i i2 2）若有右孩子，则右孩子结点编若有右孩子，则右孩子结点编 号为号为2 2i+1i+13 3）若有双亲，则双亲结点编号为若有双亲，则双亲结点编号为 (i/2)i/2)二叉树的存储结构 链式存储结构rchilddatalchilddatalchildrchild二叉链表中每个结点包含三个域：二叉链表中每个结点包含三个域：数据域、左指针数据域、左指针域和右指针域域和右指针域链式存储结构示例树的二叉链表表示树的二叉链表表示ABCDGEFABCDEFG遍历二叉树遍历：遍历：按某种搜索路径访问二叉树的每个按某种搜索路径访问二叉树的每个结点，而且每个结点仅被结点，而且每个结点仅被访问访问一次。一次。一、二叉树的遍历方法一、二叉树的遍历方法 二叉树由二叉树由根根、左子树左子树、右子树右子树三部分组成三部分组成 二叉树的遍历可以分解为：二叉树的遍历可以分解为：访问根访问根，遍历遍历左子树左子树和和遍历遍历右子树右子树约定先左后右约定先左后右,有三种遍历方法：有三种遍历方法：先序遍历、先序遍历、中序遍历、后序遍历中序遍历、后序遍历 A A F F G G E E D D C C B B 先序遍历（先序遍历（T L RT L R）若二叉树非空，若二叉树非空，（1 1）访问根结点；）访问根结点；（2 2）先序遍历左子树；）先序遍历左子树；（3 3）先序遍历右子树）先序遍历右子树；先序遍历序列：A,A,B,D,B,D,E E,G,G,C C,F F A A F F G G E E D D C C B B中序遍历（中序遍历（L T RL T R）若二叉树非空若二叉树非空（1 1）中序遍历左子树）中序遍历左子树（2 2）访问根结点）访问根结点（3 3）中序遍历右子树）中序遍历右子树中序遍历序列：D,B,G,D,B,G,E E,A,A,C,FC,F A A F F G G E E D D C C B B后序遍历（后序遍历（L R TL R T）若二叉树非空若二叉树非空（1 1）后序遍历左子树）后序遍历左子树（2 2）后序遍历右子树）后序遍历右子树（3 3）访问根结点）访问根结点后序遍历序列：D,G,D,G,E E,B,B,F,CF,C,A A A A F F G G E E D D C C B B e e d d c c b b f f a a +*/-后序遍历序列：a,b,c,d,-,*,+,a,b,c,d,-,*,+,e,f,/e,f,/,-中序遍历序列：a,+,b,*,c,-,d,a,+,b,*,c,-,d,-,e,/,fe,/,f先序遍历序列：-,+,+,a,*,b,-,c,d,a,*,b,-,c,d,/,e,f/,e,f例：先例：先序遍历、中序遍历、序遍历、中序遍历、后后序遍历下图序遍历下图所示的二叉树所示的二叉树查找基本概念基本概念若表中存在特定元素，称查找成功，应输出该记录；若表中存在特定元素，称查找成功，应输出该记录；否则，称查找不成功（也应输出失败标志或失败位置）否则，称查找不成功（也应输出失败标志或失败位置）查查 找找查找成功查找成功查找不成功查找不成功关键字关键字主关键字主关键字查询查询(Searching)特定元素特定元素(关键字）关键字）是否在表中。是否在表中。记录中某个数据项的值，可用来识别一个记录记录中某个数据项的值，可用来识别一个记录可以可以唯一唯一标识一个记录的关键字标识一个记录的关键字例如例如“学号学号”查找算法主要有：查找算法主要有：一、一、顺序查找（线性查找）顺序查找（线性查找）二、二、折半查找（二分或对分查找）折半查找（二分或对分查找）0 1 2 3 4 5 6 7（a）初态初态40803060102025(b)K=80(return i=4)80408030601020250 1 2 3 4 5 6 7(c)K=90(return i=0)0 1 2 3 4 5 6 79040803060102025 顺序查找算法：顺序查找算法：监视哨监视哨根据上述算法可知：根据上述算法可知：查找成功时的平均查找次数为：查找成功时的平均查找次数为：1+2+3+4+n)/n=(n+1)/2顺序查找的优点：顺序查找的优点：算法简单，无需排序，采用顺序算法简单，无需排序，采用顺序 和链式存储均可。和链式存储均可。顺序查找的缺点：顺序查找的缺点：平均查找长度较大。平均查找长度较大。有序表的查找（折半查找有序表的查找（折半查找/二分法查找）二分法查找）思思想想：先先确确定定待待查查找找记记录录所所在在的的范范围围，然然后后逐逐步步缩缩小小范范围，直到找到或确认找不到该记录为止。围，直到找到或确认找不到该记录为止。前提：前提：必须在必须在具有具有顺序存储结构顺序存储结构的的有序表有序表中进行中进行。分三种情况：分三种情况：1 1）若中间项的值）若中间项的值等于等于x,x,则说明已查到。则说明已查到。2 2）若）若x x小于小于中间项的值，则在线性表的前半部分查找；中间项的值，则在线性表的前半部分查找；3 3）若）若x x大于大于中间项的值，则在线性表的后半部分查找。中间项的值，则在线性表的后半部分查找。ST.elemST.elemST.lengthST.length例如例如:key=64 的查找过程如下lowlowhighhighmidmid midmid mid=(low+high)/2最理想的情况下最理想的情况下1次比较就查找成功。次比较就查找成功。查找所需时间级最多为查找所需时间级最多为O（log2n）折半查找的实现过程可以用一棵折半查找的实现过程可以用一棵二叉树二叉树来描述，树中的每个根结点对应来描述，树中的每个根结点对应当前查找区间的中间记录，它的左子树、右子树分别对应区间的左子表和右当前查找区间的中间记录，它的左子树、右子树分别对应区间的左子表和右子表，树中的每个结点对应一个记录。则上述有序序列构成的查找树如下图子表，树中的每个结点对应一个记录。则上述有序序列构成的查找树如下图所示。所示。3520186530528090第一层 查找次数 k=1第二层 查找次数 k=2第三层 查找次数 k=3第四层 查找次数 k=4 算法分析算法分析排序内部排序 排序排序将一个数据元素将一个数据元素(或记录或记录)的任意的任意序列序列,重新排列成一个按关键字有序的序列。重新排列成一个按关键字有序的序列。排序方法的分类排序方法的分类 （1）插入排序（2）交换排序（3）选择排序插入排序插入排序插入排序基本思想是插入排序基本思想是插入排序基本思想是插入排序基本思想是：插入排序有多种具体实现算法：插入排序有多种具体实现算法：插入排序有多种具体实现算法：插入排序有多种具体实现算法：1)1)直接插入排序直接插入排序直接插入排序直接插入排序 2)2)希尔排序希尔排序希尔排序希尔排序 每步将一个待排序的对象，每步将一个待排序的对象，每步将一个待排序的对象，每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象按其关键码大小，插入到前面已经排好序的一组对象按其关键码大小，插入到前面已经排好序的一组对象按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。的适当位置上，直到对象全部插入为止。的适当位置上，直到对象全部插入为止。的适当位置上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。简言之，边插入边排序，保证子序列中随时都是排好序的。简言之，边插入边排序，保证子序列中随时都是排好序的。简言之，边插入边排序，保证子序列中随时都是排好序的。1.1.直接插入排序直接插入排序直接插入排序直接插入排序直接插入排序（直接插入排序（Straight Insertion SortStraight Insertion Sort）是一种最简是一种最简单的排序方法，它的基本操作是将一个记录插到已排序好的单的排序方法，它的基本操作是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增有序表中，从而得到一个新的，记录数增1 1的有序表。的有序表。这里利用这里利用 “顺序查找顺序查找”实现实现“在在R1.i-1R1.i-1中查找中查找RiRi的插入位置的插入位置”。10.2 10.2 插插 入入 排排 序序插入插入(49)(49)：(13(13，2727，3838，4949，4949，6565，7676，97)97)插入插入(97)(97)：(38(38，4949，6565，9797)，7676，1313，2727，4949 插入插入(76)(76)：(38(38，4949，6565，7676，97)97)，1313，2727，4949 插入插入(13)(13)：(1313，3838，4949，6565，7676，97)97)，2727，4949 插入插入(27)(27)：(13(13，2727，3838，4949，6565，7676，97)97)，4949 插入插入(65)(65)：(38(38，4949，6565)，9797，7676，1313，2727，4949 例：例：4949，3838，6565，9797，7676，1313，2727，4949 插入插入(38)(38)：(3838，49)49)，6565，9797，7676，1313，2727，4949 初始序列：初始序列：(4949)，3838，6565，9797，7676，1313，2727，4949 对于有对于有n个数据元个数据元素的待排序列，素的待排序列，插入操作要进行插入操作要进行n-1次次时间：时间：最好情形最好情形判断判断n次，无移动；次，无移动；故时间复杂度：故时间复杂度：O(n2)适用于：适用于：一边输入数据、一边排序一边输入数据、一边排序直接插入排序算法分析直接插入排序算法分析2.2.希尔（希尔（希尔（希尔（shellshell）排序（又称缩小增量排序排序（又称缩小增量排序排序（又称缩小增量排序排序（又称缩小增量排序）基本思想基本思想基本思想基本思想：先将整个待排记录序列分割成若干子序列：先将整个待排记录序列分割成若干子序列：先将整个待排记录序列分割成若干子序列：先将整个待排记录序列分割成若干子序列,分别进分别进分别进分别进行直接插入排序，待整个序列中的记录行直接插入排序，待整个序列中的记录行直接插入排序，待整个序列中的记录行直接插入排序，待整个序列中的记录“基本有序基本有序基本有序基本有序”时，再时，再时，再时，再对全体记录进行一次直接插入排序。对全体记录进行一次直接插入排序。对全体记录进行一次直接插入排序。对全体记录进行一次直接插入排序。技巧：技巧：技巧：技巧：子序列的构成不是简单地子序列的构成不是简单地子序列的构成不是简单地子序列的构成不是简单地“逐段分割逐段分割逐段分割逐段分割”，而是将相隔，而是将相隔，而是将相隔，而是将相隔某个增量某个增量某个增量某个增量dkdkdkdk的的的的记录组成一个子序列记录组成一个子序列记录组成一个子序列记录组成一个子序列,让增量让增量让增量让增量dkdkdkdk逐逐逐逐趟缩短趟缩短趟缩短趟缩短(例如例如例如例如依次取依次取依次取依次取5,3,1)5,3,1)5,3,1)5,3,1)，直到，直到，直到，直到dkdkdkdk1 1 1 1为止。为止。为止。为止。优点：优点：优点：优点：让关键字值小的元素能很快前移，且序列若基本有序让关键字值小的元素能很快前移，且序列若基本有序让关键字值小的元素能很快前移，且序列若基本有序让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。时，再用直接插入排序处理，时间效率会高很多。时，再用直接插入排序处理，时间效率会高很多。时，再用直接插入排序处理，时间效率会高很多。具体实现具体实现具体实现具体实现:首首先先选选定定两两个个记记录录间间的的距距离离d1d1，在在整整个个待待排排序序记记录录序序列列中中将将所所有有间间隔隔为为d1d1的的记记录录分分成成一一组，进行组内直接插入排序，组，进行组内直接插入排序，然然后后再再取取两两个个记记录录间间的的距距离离d2d1d2d1，在在整整个个待待排排序序记记录录序序列列中中，将将所所有有间间隔隔为为d2d2的的记记录录分分成一组，进行组内直接插入排序成一组，进行组内直接插入排序 直直至至选选定定两两个个记记录录间间的的距距离离dtdt=1=1为为止止，此此时只有一个子序列，即整个待排序记录序列。时只有一个子序列，即整个待排序记录序列。例如：1 2 3 4 5 6 7 8 9 10关键字：49 38 65 97 76 13 27 49*55 04第一趟希尔排序，设增量 d=5，分为分为5组组，各组内进行直接插入排序13 27 49*55 04 49 38 65 97 76第二趟希尔排序，设增量 d=3，分为分为3组组，各组内进行直接插入排序13 04 49*38 27 49 55 65 97 76 04 13 27 38 49*49 55 65 76 97第三趟希尔排序，设增量 d=1，分为分为1组组，各组内进行直接插入排序时间效率：时间效率：时间效率：时间效率：当增量序列为当增量序列为当增量序列为当增量序列为d(k)=2d(k)=2t-k+1t-k+1-1-1时，时间复杂度为时，时间复杂度为时，时间复杂度为时，时间复杂度为O O(n n1.51.5）。交换排序交换排序 两两比较待排序记录的关键两两比较待排序记录的关键两两比较待排序记录的关键两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好码，如果发生逆序（即排列顺序与排序后的次序正好码，如果发生逆序（即排列顺序与排序后的次序正好码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。相反），则交换之，直到所有记录都排好序为止。相反），则交换之，直到所有记录都排好序为止。相反），则交换之，直到所有记录都排好序为止。交换排序的主要算法有：交换排序的主要算法有：交换排序的主要算法有：交换排序的主要算法有：1)1)冒泡排序冒泡排序冒泡排序冒泡排序 2)2)快速排序快速排序快速排序快速排序交换排序基本思想是交换排序基本思想是交换排序基本思想是交换排序基本思想是：1 1 冒泡排序冒泡排序冒泡排序冒泡排序基本思路：基本思路：基本思路：基本思路：每趟不断将记录两两比较，并按每趟不断将记录两两比较，并按每趟不断将记录两两比较，并按每趟不断将记录两两比较，并按“前小后大前小后大前小后大前小后大”（或（或（或（或“前大后小前大后小前大后小前大后小”）规则交换。）规则交换。）规则交换。）规则交换。优点：优点：优点：优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还每趟结束时，不仅能挤出一个最大值到最后面位置，还每趟结束时，不仅能挤出一个最大值到最后面位置，还每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还能同时部分理顺其他元素；一旦下趟没有交换发生，还能同时部分理顺其他元素；一旦下趟没有交换发生，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。可以提前结束排序。可以提前结束排序。可以提前结束排序。前提：前提：前提：前提：顺序存储结构顺序存储结构顺序存储结构顺序存储结构 rj rj+1 ri+1 rn-1 rn 无无序区序区 有序区有序区 1ji-1 位于最终位置位于最终位置反序则交换反序则交换2 21 10 08 82 25 5 4 49 9 2 25 5 1 16 62 21 14 49 92 25 5 2 25 5 1 16 6 0 08 82 21 14 49 92 25 52 25 51 16 6 0 08 82 21 14 49 92 25 5 2 25 51 16 6 0 08 82 21 14 49 92 25 5 2 25 51 16 6 0 08 8初始关键字第一趟排序第四趟排序第二趟排序第三趟排序2 21 14 49 92 25 5 2 25 51 16 60 08 8第五趟排序起泡排序的过程起泡排序的过程最大者最大者沉底沉底冒泡排序的算法分析冒泡排序的算法分析时间效率：时间效率：O O（n n2 2)因为要考虑最坏情况因为要考虑最坏情况空间效率：空间效率：O O（1 1）只在交换时用到一个缓冲只在交换时用到一个缓冲单元单元2.2.快速排序快速排序(对冒泡的改进对冒泡的改进)从待排序列中任取一个元素从待排序列中任取一个元素从待排序列中任取一个元素从待排序列中任取一个元素 (例如取第一个例如取第一个例如取第一个例如取第一个)作为作为作为作为中心，所有比它小的元素一律前放，所有比它大的元素一中心，所有比它小的元素一律前放，所有比它大的元素一中心，所有比它小的元素一律前放，所有比它大的元素一中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中律后放，形成左右两个子表；然后再对各子表重新选择中律后放，形成左右两个子表；然后再对各子表重新选择中律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。心元素并依此规则调整，直到每个子表的元素只剩一个。心元素并依此规则调整，直到每个子表的元素只剩一个。心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。此时便为有序序列了。此时便为有序序列了。此时便为有序序列了。基本思想：基本思想：基本思想：基本思想：优点：优点：优点：优点：因为每趟可以确定不止一个元素的位置，而且呈指数增因为每趟可以确定不止一个元素的位置，而且呈指数增因为每趟可以确定不止一个元素的位置，而且呈指数增因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！加，所以特别快！加，所以特别快！加，所以特别快！前提：前提：前提：前提：顺序存储结构顺序存储结构顺序存储结构顺序存储结构 ()()，设以首元素为枢轴中心设以首元素为枢轴中心设以首元素为枢轴中心设以首元素为枢轴中心 关键字序列关键字序列关键字序列关键字序列 T=(21T=(21，2525，4949，25*25*，1616，0808），），），），请请请请写出快速排序的算法步骤。写出快速排序的算法步骤。写出快速排序的算法步骤。写出快速排序的算法步骤。2121，2525，4949，2525*，1616，0808初态：初态：初态：初态：第第第第1 1趟：趟：趟：趟：第第第第2 2趟：趟：趟：趟：第第第第3 3趟：趟：趟：趟：0808，1616，2121，2525，25*25*，(4949)21211616，0808，()()2525，25*25*，4949(0808)，1616，2121，2525，(25*25*，4949)快速排序的过程快速排序的过程快速排序分析快速排序分析n快速排序的快速排序的平均时间平均时间为为T(n)=T(n)=nlog(nnlog(n)n经验表明经验表明,在同数量级的排序方法中在同数量级的排序方法中,快速排序的快速排序的常数因子常数因子k k最小最小.n就就平均时间平均时间而言而言,快速排序是快速排序是最好最好的的.n若初始序列若初始序列按关键字基本有序按关键字基本有序,快速排序蜕化为快速排序蜕化为起泡排序起泡排序,其时间复杂度为其时间复杂度为O(nO(n2 2)。选择排序选择排序有多种具体实现算法：选择排序有多种具体实现算法：1)简单选择排序简单选择排序 2)堆排序堆排序选择排序的基本思想是：每一趟在后面选择排序的基本思想是：每一趟在后面选择排序的基本思想是：每一趟在后面选择排序的基本思想是：每一趟在后面n-in-i 个待排记录中个待排记录中个待排记录中个待排记录中选取关键字最小的记录作为有序序列中的第选取关键字最小的记录作为有序序列中的第选取关键字最小的记录作为有序序列中的第选取关键字最小的记录作为有序序列中的第i i 个记录。个记录。个记录。个记录。1 1 简单选择排序简单选择排序思思思思路路路路简简简简单单单单：每每每每经经经经过过过过一一一一趟趟趟趟比比比比较较较较就就就就找找找找出出出出一一一一个个个个最最最最小小小小值值值值，与与与与待待待待排序列最前面的位置互换即可。排序列最前面的位置互换即可。排序列最前面的位置互换即可。排序列最前面的位置互换即可。首首首首先先先先，在在在在n n个个个个记记记记录录录录中中中中选选选选择择择择最最最最小小小小者者者者放放放放到到到到r1r1位位位位置置置置；然然然然后后后后，从从从从剩剩剩剩余余余余的的的的n-1n-1个个个个记记记记录录录录中中中中选选选选择择择择最最最最小小小小者者者者放放放放到到到到r2r2 位位位位置置置置；如如如如此此此此进进进进行行行行下下下下去去去去，直到全部有序为止。直到全部有序为止。直到全部有序为止。直到全部有序为止。优点：实现简单优点：实现简单优点：实现简单优点：实现简单缺点：每趟只能确定一个元素，表长为缺点：每趟只能确定一个元素，表长为缺点：每趟只能确定一个元素，表长为缺点：每趟只能确定一个元素，表长为n n n n时需要时需要时需要时需要n-1n-1n-1n-1趟趟趟趟前提：顺序存储结构前提：顺序存储结构前提：顺序存储结构前提：顺序存储结构 效率分析效率分析 简单选择排序比较次数与关键字初始排序无关。简单选择排序比较次数与关键字初始排序无关。找找第第一一个个最最小小记记录录需需进进行行n-1次次比比较较，找找第第二二个个最最小小记记录录需需要要比比较较n-2次次，找找第第i个个最最小小记记录录需需要要进进行行n-i次次比比较较，总的比较次数为：总的比较次数为：（n-1）+（n-2）+（n-i）+2+1=n(n-1)/2=n2/2 时间复杂度：时间复杂度：O(n2)辅助空间：辅助空间：O（1）简单选择排序是不稳定的排序方法。简单选择排序是不稳定的排序方法。2 2 堆排序堆排序1.1.1.1.什么是堆？什么是堆？什么是堆？什么是堆？堆的定义：设有堆的定义：设有堆的定义：设有堆的定义：设有n n个元素的序列个元素的序列个元素的序列个元素的序列 k k1 1，k k2 2，k kn n，当且仅当且仅当且仅当且仅当满足下述关系之一时，称之为堆。当满足下述关系之一时，称之为堆。当满足下述关系之一时，称之为堆。当满足下述关系之一时，称之为堆。k ki i k k2i2ik ki i k k2i+12i+1k ki i k k2i2ik ki i k k2i+12i+1或者或者或者或者i=1,2,n/2i=1,2,n/2解释：如果让满足以上条件的元素序列解释：如果让满足以上条件的元素序列解释：如果让满足以上条件的元素序列解释：如果让满足以上条件的元素序列 （k k1 1，k k2 2，k kn n）顺次排成一棵完全二叉树，则此树的特点是：顺次排成一棵完全二叉树，则此树的特点是：顺次排成一棵完全二叉树，则此树的特点是：顺次排成一棵完全二叉树，则此树的特点是：树中所有结点的值均大于（或小于）其左右孩子，此树的根树中所有结点的值均大于（或小于）其左右孩子，此树的根树中所有结点的值均大于（或小于）其左右孩子，此树的根树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。结点（即堆顶）必最大（或最小）。结点（即堆顶）必最大（或最小）。结点（即堆顶）必最大（或最小）。2.2.2.2.怎样建堆？怎样建堆？怎样建堆？怎样建堆？3.3.3.3.怎样堆排序？怎样堆排序？怎样堆排序？怎样堆排序？小根小根堆堆 8 81616 9 9 1 1 6 6 2 2 11111010 5 5 4 4大根大根堆堆1616 9 9 8 81010 6 6 2 2 1111 1 1 5 5 4 4 1 1 6 6 8 81212 9 91616 2 2 1111 5 51414 1 1 9 9 8 81010 6 61616 2 2 1111 5 5 4 4不是不是堆堆不是不是堆堆算法分析算法分析 堆排序方法对记录数较少的文件并不堆排序方法对记录数较少的文件并不值得提倡值得提倡,但对但对n n较大的文件还是很有效的较大的文件还是很有效的.因为其运行时间主要耗费在建初始堆和调因为其运行时间主要耗费在建初始堆和调整新堆时进行的反复整新堆时进行的反复“筛选筛选”上。上。堆排序在最坏情况下，其时间复杂度堆排序在最坏情况下，其时间复杂度也为也为O O（nlognlog2 2n),n),相对于快速排序来说，这相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需是堆排序的最大优点。此外，堆排序仅需一个记录大小供交换用的辅助存储空间。一个记录大小供交换用的辅助存储空间。