第一章数据结构

《第一章数据结构》由会员分享，可在线阅读，更多相关《第一章数据结构（87页珍藏版）》请在装配图网上搜索。

1、全国计算机等级考试公共基础知识 全国计算机等级考试二级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，

2、余数为，余数为0；答答:112和和64的最大公约数为的最大公约数为16。引入算法引入算法算法的五个重要算法的五个重要特性特性算法：算法：基本特征基本特征（1）有穷性：有穷性：算法必须在执行有穷步之后结束，每一算法必须在执行有穷步之后结束，每一步都可在有穷时间内完成。步都可在有穷时间内完成。（2）确定性：确定性：对相同的输入只能得出相同的输出。对相同的输入只能得出相同的输出。（3）可行性：可行性：算法所描述的操作都是可实现的。算法所描述的操作都是可实现的。（4）拥有足够的情报。拥有足够的情报。算法设计的要求算法设计的要求 （1）正确性：正确性：算法应当满足具体问题的需求；算法应当满足具体问题的需

3、求；（2）可读性：可读性：可读性好的算法有助人们于对可读性好的算法有助人们于对算法的理解；算法的理解；（3）健壮性：健壮性：当输入非法数据时，算法也能当输入非法数据时，算法也能适当地做出反应或进行处理，而不会产生莫名适当地做出反应或进行处理，而不会产生莫名其妙的输出结果；其妙的输出结果；（4）效率与低存贮量：效率与低存贮量：效率指的是算法执行效率指的是算法执行的时间，解决同一问题，执行时间短的算法效的时间，解决同一问题，执行时间短的算法效率高。存储量指算法执行过程中所需要的最大率高。存储量指算法执行过程中所需要的最大存储空间。存储空间。算法基本要素算法基本要素一个算法通常由两个基本要素所组成：

4、一个算法通常由两个基本要素所组成：1.对数据对象的运算和操作对数据对象的运算和操作2.算法的控制结构算法的控制结构基本运算和操作分为四类：基本运算和操作分为四类：1.算术运算算术运算 2.逻辑运算逻辑运算 3.关系运算关系运算 4.数据传输数据传输算法的控制结构：算法的控制结构：顺序顺序 选择选择 循环循环 算法优劣分析算法优劣分析 同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度时间复杂度和空间复杂度空间复杂度来考虑。时间复杂度 是指执行算法所需要的计算工作量，是由算法执行的基本运算次数来度量。

5、空间复杂度是指算法在计算机内执行时所需的内存空间。数据结构数据结构现实中对象之间的关系 线性关系：如列车中各车箱之间的关系、排队买车票线性关系：如列车中各车箱之间的关系、排队买车票人之间的关系、一叠盘子中各盘子之间的关系等。人之间的关系、一叠盘子中各盘子之间的关系等。层次关系：如学校的组织结构、人的辈分关系等。层次关系：如学校的组织结构、人的辈分关系等。网状关系：如城市铁路交通网、电话网、计算机网络网状关系：如城市铁路交通网、电话网、计算机网络等。等。应用举例1学籍档案管理假设一个学籍档案管理系统应包含如下表1-1所示的学生信息。特点：l每个学生的信息占据一行，所有学生的信息按学号顺序依次排列

6、构成一张表格；l表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；l对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。数据结构主要研究以下三个方面的问题：数据结构主要研究以下三个方面的问题：数据的逻辑结构数据的存储结构对各种数据结构进行的运算 注意：注意：讨论以上问题讨论以上问题主要目的主要目的是为了是为了提高数据处理的提高数据处理的效率效率，提高效率包括两个方面：，提高效率包括两个方面：一是提高数据处理的速度一是提高数据处理的速度二是节省在数据处理过程中所占用的计算机二是节省在数据处理过程中所占用的计算机存储

7、空间存储空间 数据结构概论数据结构概论数据：数据：能输入到计算机中并被计算机存储、能输入到计算机中并被计算机存储、加工的符号的总称。（数值型、布尔型、字加工的符号的总称。（数值型、布尔型、字符串、表格、语音、图片、图像等）符串、表格、语音、图片、图像等）数据元素：数据元素：数据的数据的基本基本单位（结点、顶点或单位（结点、顶点或记录）记录）通常作为一个整体进行处理。通常作为一个整体进行处理。数据项：数据项：数据的不可分割的数据的不可分割的最小最小单位。单位。一个数据元素可以由若干个数据项构成。一个数据元素可以由若干个数据项构成。逻辑结构逻辑结构1.数据的逻辑结构分为线性结构和非线性结构两大类。

8、数据的逻辑结构分为线性结构和非线性结构两大类。(1)线性结构线性结构:包括数组、链表、包括数组、链表、栈、队列、优先级队列等栈、队列、优先级队列等;线性结构的基本特征线性结构的基本特征存在唯一的存在唯一的“第一个第一个”数据元素；数据元素；存在唯一的存在唯一的“最后一个最后一个”数据元素；数据元素；除第一个外，每个数据元素均有且只有一个除第一个外，每个数据元素均有且只有一个直接前驱直接前驱元素；元素；除最后一个外，每个数据元素均有且只有一个除最后一个外，每个数据元素均有且只有一个直接后继直接后继元素。元素。(2)非线性结构非线性结构:包括树、图等包括树、图等.答：指数据元素之间的逻辑关系。即从

9、逻辑关系上描述答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。数据，它与数据的存储无关，是独立于计算机的。何为数据的逻辑结构？何为数据的逻辑结构？存存 储储 结结 构构存储结构概念：数据的逻辑结构在计算机存储空间中的存放存储结构概念：数据的逻辑结构在计算机存储空间中的存放形式形式常见存储结构：常见存储结构：(1)顺序存储结构：顺序存储结构：特点是借助于数据元素的相对存储位特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构置来表示数据元素之间的逻辑结构.即逻辑上相邻即逻辑上相邻,物理上也相邻物理上也相邻.(2)链式存储结构：链式存储结构：特

10、点是借助于指示数据元素地址的指特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。针表示数据元素之间的逻辑结构。(3)索引存储结构索引存储结构:线性表线性表的概念线性表的概念 线性表：线性表：是线性结构的一种具体表现，所含结是线性结构的一种具体表现，所含结点的个数称为表长，表长为点的个数称为表长，表长为0的线性表称为的线性表称为空表。空表。春春夏夏秋秋冬冬 线性表线性表（a1,a2,ai,ai+1,an）的的顺序表示：顺序表示：用一组用一组地址连续地址连续的存贮单元的存贮单元依次存贮依次存贮线性表的数据元素。线性表的数据元素。顺序表的顺序表的特点：逻辑结构中相邻特点：逻辑结构中相邻的

11、结点在的结点在存储结构中仍相邻存储结构中仍相邻。顺序表的顺序表的容量容量（maxsize）：线性表实际）：线性表实际达到的最大长度。达到的最大长度。表长表长：当前表的长度，小于等于表的容量。：当前表的长度，小于等于表的容量。线性表的顺序存储结构线性表的顺序表示（图示）线性表的顺序表示（图示）b数据元素数据元素a1的存储地址的存储地址l每个数据元素所需的存储单元大小每个数据元素所需的存储单元大小存储地址存储地址bb+lb+(i-1)lb+(n-1)l内存状态内存状态a1a2aian位序位序 1 2 I n 插入运算：插入运算：在表的第在表的第i(1=i=n+1)个位置个位置上，插入一个新结点上，

12、插入一个新结点x，使长度为，使长度为n的线性的线性表变成长度为表变成长度为n+1的线性表的线性表 插入算法的基本插入算法的基本步骤步骤：将结点将结点ai,an各各后移后移一位；一位；将新结点将新结点x置入第置入第i个位置；个位置；表长加表长加1 插入一个元素所需平均插入一个元素所需平均移动次数：移动次数：n/2线性表的插入运算在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：1213212428304277121321242830427712345678123456789插入插入 删除运算：删除运算：将表的第将表的第i(1=inext是否为空，而

13、是它们是是否为空，而是它们是否等于头指针。否等于头指针。循环链表循环链表Ha1a2a3Haian双向链表双向链表 双向链表双向链表的的特点特点表中的每个结点有表中的每个结点有两个指针域，一个指向后继结点，一个两个指针域，一个指向后继结点，一个指向前趋结点，指向前趋结点，整个链表形成两个环。整个链表形成两个环。从表的任意结点出发可以通过正向环从表的任意结点出发可以通过正向环（或反向环）找到表中其它结点。（或反向环）找到表中其它结点。priordatanext结点：结点：LL35栈和队列36“取”操作必须在这端进行“放”操作必须在同一端进行栈栈 栈（栈（stack）:先进后出先进后出(FILO）的

14、线性表。的线性表。或或后进先出（后进先出（LIFO）的线性表。的线性表。或仅在或仅在表尾表尾进行进行插入插入和和删除删除操作的线性表。操作的线性表。栈顶（栈顶（top）:线性表的线性表的表尾端表尾端，即可操作端。，即可操作端。栈底（栈底（bottom）:线性表的线性表的表头表头。栈底栈底栈顶栈顶.a1a2a3an-1an入栈入栈(push)出栈出栈(pop)栈的基本操作 进栈操作进栈操作 ：将数据元素将数据元素x x插入栈插入栈S S，使，使x x成为成为S S的栈顶元素；的栈顶元素；出栈操作：出栈操作：当栈不空时返回栈顶元素为该函数的值，然后删除栈顶当栈不空时返回栈顶元素为该函数的值，然后删

15、除栈顶元素；元素；取栈顶元素取栈顶元素 ：当栈不空时返回栈顶元素为该函数的值，但栈顶保持不当栈不空时返回栈顶元素为该函数的值，但栈顶保持不变；变；队列 排队只能排在尾部,排在对头的先得到服务;“插队”是不允许的.换言之,插入和删除只能在线性表的两头分别进行;插入的一端称为队尾,删除的一端称为队头;其特点是:先进先出(FIFO)队列(Queues)是生活中“排队”的抽象 队列队列（Queue）:先进先出先进先出(First In First Out)(缩写为缩写为FIFO）的线性表。）的线性表。仅在仅在队尾队尾进行进行插入插入和和队头队头进行进行删除删除操作的线操作的线性表。性表。队头队头（fr

16、ont）:线性表的表头端，即线性表的表头端，即可删除端可删除端。队尾队尾（rear）:线性表的表尾端，即线性表的表尾端，即可插入端可插入端。队头队头队尾队尾.a1a2a3an-1an入队列入队列(Enqueue)出队列出队列(Dequeque)循环队列（队列的顺序表示与实现）采用顺序存储结构采用顺序存储结构约定约定:1)初始空队列：初始空队列：front=rear=0;2)循环队列中元素个数循环队列中元素个数=rear-front rear front102354J1J2J3 front rearJ3 front rearJ5J6 front rear树和二叉树树和二叉树一对多一对多社会的组织

17、结构社会的组织结构家族的族谱家族的族谱计算机中目录组织计算机中目录组织树的类型定义树的类型定义 树是一类重要的非线性数据结构，是以分支关系定义的层次结构。即树的数据元素即树的数据元素一个结点所拥有的后件一个结点所拥有的后件的个数的个数结点结点结点的度结点的度 根根 叶子叶子树的度树的度树的深度树的深度(或高度或高度)即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)所有结点度中的最大值（所有结点度中的最大值（Max各结点的度各结点的度）指所有结点中最大的层数（指所有结点中最大的层数（Max各结点的层次各结点的层次）问：问：右上图中的结点数右上图中的结点数 ；树的度；树

18、的度 ；树的深度；树的深度13133 34 4（有几个直接后继就是几度）（有几个直接后继就是几度）ABCGEIDHFJFLK二叉树二叉树的五种基本形态：二叉树的五种基本形态：(c)右子树为空的二叉树右子树为空的二叉树(d)左、右子树均为非空的二叉树左、右子树均为非空的二叉树(e)左子树为空的二叉树左子树为空的二叉树(a)A(b)A(c)A(d)A(e)(a)空二叉树空二叉树(b)仅有根结点的二叉树仅有根结点的二叉树逻辑结构：逻辑结构：一对二（一对二（1:2）基本特征基本特征:每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2 2的结点）；的结点）；左子树和右子树次序

19、不能颠倒。左子树和右子树次序不能颠倒。二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。树的、互不交的二叉树组成。两种特殊的二叉树两种特殊的二叉树1.1.满二叉树：满二叉树：一颗树中所有叶结点均在同一阶一颗树中所有叶结点均在同一阶层，而其它非终端结点的分支度均为层，而其它非终端结点的分支度均为2 2，则此，则此树为一颗满二叉树。树为一颗满二叉树。若该树的高度为若该树的高度为h h，则此满二叉树的结点为，则此满二叉树的结点为2 2h-1h-1。2.完全二叉树：完全二叉树：如果一颗二叉树只有最下一层如果

20、一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树；中在该层的最左端，则称为完全二叉树；二叉树的性质（重要）性质性质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对完全二叉树的结点编号：对完全二叉

21、树的结点编号：从上到下，从左到右从上到下，从左到右 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）若有左孩子，则左孩编号为）若有左孩子，则左孩编号为2i2i2 2）若有右孩子，则右孩子结点编）若有右孩子，则右孩子结点编 号为号为2i+12i+13 3）若有双亲，则双亲结点编号为）若有双亲，则双亲结点编号为 (i/2)(i/2)二叉树的存储结构 链式存储结构r

22、childdatalchilddatalchildrchild二叉链表中每个结点包含三个域：二叉链表中每个结点包含三个域：数据域、左指针数据域、左指针域和右指针域域和右指针域链式存储结构示例树的二叉链表表示树的二叉链表表示ABCDGEFABCDEFG遍历二叉树遍历：遍历：按某种搜索路径访问二叉树的每个按某种搜索路径访问二叉树的每个结点，而且每个结点仅被结点，而且每个结点仅被访问访问一次。一次。一、二叉树的遍历方法一、二叉树的遍历方法 二叉树由二叉树由根根、左子树左子树、右子树右子树三部分组成三部分组成 二叉树的遍历可以分解为：二叉树的遍历可以分解为：访问根访问根，遍历遍历左子树左子树和和遍历遍

23、历右子树右子树约定先左后右约定先左后右,有三种遍历方法：有三种遍历方法：先序遍历、先序遍历、中序遍历、后序遍历中序遍历、后序遍历 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）中序遍历左子树）中序遍

24、历左子树（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

25、,c,d,-,*,+,+,e,f,/e,f,/,-中序遍历序列：a,+,b,a,+,b,*,c,-,d,c,-,d,-,e,/,fe,/,f先序遍历序列：-,+,a,+,a,*,b,-,c,d,b,-,c,d,/,e,f/,e,f例：先例：先序遍历、中序遍历、序遍历、中序遍历、后后序遍历下图序遍历下图所示的二叉树所示的二叉树查找基本概念基本概念若表中存在特定元素，称查找成功，应输出该记录；若表中存在特定元素，称查找成功，应输出该记录；否则，称查找不成功（也应输出失败标志或失败位置）否则，称查找不成功（也应输出失败标志或失败位置）查查 找找查找成功查找成功查找不成功查找不成功关键字关键字主关键字

26、主关键字查询查询(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

27、)0 1 2 3 4 5 6 79040803060102025 顺序查找算法：顺序查找算法：监视哨监视哨根据上述算法可知：根据上述算法可知：查找成功时的平均查找次数为：查找成功时的平均查找次数为：1+2+3+4+n)/n=(n+1)/2顺序查找的优点：顺序查找的优点：算法简单，无需排序，采用顺序算法简单，无需排序，采用顺序 和链式存储均可。和链式存储均可。顺序查找的缺点：顺序查找的缺点：平均查找长度较大。平均查找长度较大。有序表的查找（折半查找有序表的查找（折半查找/二分法查找）二分法查找）思想：思想：先确定待查找记录所在的范围，然后逐步缩小范先确定待查找记录所在的范围，然后逐步缩小范围，直

28、到找到或确认找不到该记录为止。围，直到找到或确认找不到该记录为止。前提：前提：必须在必须在具有具有顺序存储结构顺序存储结构的的有序表有序表中进行中进行。分三种情况：分三种情况：1 1）若中间项的值）若中间项的值等于等于x,x,则说明已查到。则说明已查到。2 2）若）若x x小于小于中间项的值，则在线性表的前半部分查找；中间项的值，则在线性表的前半部分查找；3 3）若）若x x大于大于中间项的值，则在线性表的后半部分查找。中间项的值，则在线性表的后半部分查找。例如例如:key=64 的查找过程如下mid=(low+high)/2最理想的情况下最理想的情况下1次比较就查找成功。次比较就查找成功。查

29、找所需时间级最多为查找所需时间级最多为O（log2n）折半查找的实现过程可以用一棵折半查找的实现过程可以用一棵二叉树二叉树来描述，树中的每个根结点对来描述，树中的每个根结点对应当前查找区间的中间记录，它的左子树、右子树分别对应区间的左子表和应当前查找区间的中间记录，它的左子树、右子树分别对应区间的左子表和右子表，树中的每个结点对应一个记录。则上述有序序列构成的查找树如下右子表，树中的每个结点对应一个记录。则上述有序序列构成的查找树如下图所示。图所示。3520186530528090第一层 查找次数 k=1第二层 查找次数 k=2第三层 查找次数 k=3第四层 查找次数 k=4 算法分析算法分析

30、排序内部排序 排序排序将一个数据元素将一个数据元素(或记录或记录)的任意的任意序列序列,重新排列成一个按关键字有序的序列。重新排列成一个按关键字有序的序列。排序方法的分类排序方法的分类 （1）插入排序（2）交换排序（3）选择排序插入排序插入排序直接插入排序（直接插入排序（Straight Insertion SortStraight Insertion Sort）是一种最简）是一种最简单的排序方法，它的基本操作是将一个记录插到已排序好的单的排序方法，它的基本操作是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增有序表中，从而得到一个新的，记录数增1 1的有序表。的有序表。这里利用这

31、里利用“顺序查找顺序查找”实现实现“在在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

32、插入插入(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个数据元个数据元素的待排序列，素的待排序列，插入操作要进

33、行插入操作要进行n-1次次时间：时间：最好情形最好情形判断判断n次，无移动；次，无移动；故时间复杂度：故时间复杂度：O(n2)适用于：适用于：一边输入数据、一边排序一边输入数据、一边排序直接插入排序算法分析直接插入排序算法分析2.希尔（希尔（shell）排序（又称缩小增量排序）排序（又称缩小增量排序具体实现具体实现例如：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组

34、组，各组内进行直接插入排序13 04 49*38 27 49 55 65 97 76 04 13 27 38 49*49 55 65 76 97第三趟希尔排序，设增量 d=1，分为分为1组组，各组内进行直接插入排序 时间效率：时间效率：交换排序交换排序 1 冒泡排序冒泡排序rj rj+1 ri+1 rn-1 rn 无序区无序区 有序区有序区 1ji-1 位于最终位置位于最终位置反序则交换反序则交换初始关键字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序起泡排序的过程起泡排序的过程最大者最大者沉底沉底冒泡排序的算法分析冒泡排序的算法分析 关键字序列关键字序列 T=(21，25，49，25*，

35、16，08），），请写出快速排序的算法步骤。请写出快速排序的算法步骤。快速排序的过程快速排序的过程快速排序分析快速排序分析n快速排序的快速排序的平均时间平均时间为为T(n)=nlog(n)T(n)=nlog(n)n经验表明经验表明,在同数量级的排序方法中在同数量级的排序方法中,快速排序的快速排序的常数因子常数因子k k最小最小.n就就平均时间平均时间而言而言,快速排序是快速排序是最好最好的的.n若初始序列若初始序列按关键字基本有序按关键字基本有序,快速排序蜕化为快速排序蜕化为起泡排序起泡排序,其时间复杂度为其时间复杂度为O(nO(n2 2)。效率分析效率分析 简单选择排序比较次数与关键字初始排

36、序无关。简单选择排序比较次数与关键字初始排序无关。找第一个最小记录需进行找第一个最小记录需进行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）简单选择排序是不稳定的排序方法。简单选择排序是不稳定的排序方法。小根小根堆堆 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不是不是堆堆不是不是堆堆