计算机二级-数据结构及算法课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.,基本数据结构与算法,(10.22%),1.1,算法,(0.82%),1.1.1,算法,(algorithm),基本概念,定义：算法是指解题方案的准确而完整的描述。算法不等于程序，不等于计算方法。只能说程序是算法的一种描述，所以，程序不可能优于算法的设计。算法是指一系列解决问题的清晰指令。,特征：算法具有,可行性,、,确定性,、,有穷性,、,输入,和,输出（拥有足够的情报）,等个重要特性。,1.1.2,算法的基本要素,1,、对数据的运算和操作,算术运算,逻辑运算,关系运算,数据传输,2,、算法的控制结构,算法中各操作之间的执行顺序,描述算法的工具通常有传统流程图、,N-S,结构化流程图、算法描述语言等,一个算法一般可以用,顺序、选择、循环,三种基本机构组合而成。,1.1.3,算法设计基本方法,列举法,归纳法,递推,递归,减半递推技术,回溯法,1.2,算法复杂度,1.2.1,时间复杂度,所谓算法的时间复杂度，是指执行算法所需要的计算工作量。,可以用算法在执行过程中所需要的基本运算的执行次数来度量算法的工作量。,1.2.2,算法的空间复杂度,一般是指执行这个算法所需要的内存空间,一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及某种数据结构所需要的附加存储空间,1.2,数据结构,(0.96%),数据结构的定义,数据的逻辑结构和存储结构,数据结构的图形表示,线性结构与非线性结构,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,1.2.2,基本概念和术语,能输入到计算机中,并能被计算机程序处理的,符号的集合。,整数,(1,2),、实数,(1.1,1.2),字符串,(Beijing),、,图形、声音。,1.2.2,基本概念和术语,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,1.2.2,基本概念和术语,计算机管理图书问题,在图书馆里有各种卡片：有按书名编排的、,有按作者编排的、有按分类编排,如何将查询图书的这些信息存入计算机中,既要考虑查询时间短，又要考虑节省空间,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,最简单的办法之一是建立一张表，,每一本书的信息在表中占一行，如,1.2.2,基本概念和术语,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,如何将,0,1,2,3,4,5,6,7,8,9,这,10,个数存放在,计算机中能最快地达到你所需要的目的？,目的不同，最佳的存储方方法就不同。,从大到小排列：,9,8,7,6,5,4,3,2,1,0,输出偶数：,0,2,4,6,8,1,3,5,7,9,数据元素在,计算机中的表示,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,1.2.2,基本概念和术语,对数据结构中的节点进行,操作处理,(,插入、删除、修改、查找、排序,),1.2.2,基本概念和术语,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,数据元素,(Data Element),数据元素是数据的基本单位，即数据集合中的个体。,有时一个数据元素可由若干,数据项,(Data Item),组成。数据项是数据的最小单位。,数据元素亦称,节点,或,记录,。,数据结构可描述为,B=,（,D,，,R,）,有限个数据元素的集合,有限个节点间关系的集合,1,数据的逻辑结构,2,、数据的存储（物理）结构,3,、数据的运算：检索、排序、插入、删除、修改等。,A,线性结构,B,非线性结构,A,顺序存储,B,链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,数据结构可描述为,B=,（,D,，,R,）,线性结构,A,B,C,，,X,Y,Z,学 生 成 绩 表,86,胡孝臣,9861103,95,刘忠赏,9861107,100,张卓,9861109,成绩,姓名,学号,线性表,结点间是以线性关系联结,1,数据的逻辑结构,2,、数据的存储结构,3,、数据的运算：检索、排序、插入、删除、修改等。,A,线性结构,B,非线性结构,A,顺序存储,B,链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,数据结构可描述为,B=,（,D,，,R,）,树形结构,全校学生档案管理的组织方式,计算机程序管理系统也是典型的树形结构,A,B,C,D,E,F,G,H,树形结构,结点间具有分层次的连接关系,H,B,C,D,E,F,G,A,1,数据的逻辑结构,2,、数据的存储结构,3,、数据的运算：检索、排序、插入、删除、修改等。,A,线性结构,B,非线性结构,A,顺序存储,B,链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(,亦称物理结构,),1,4,2,3,D=1,2,3,4,R=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4),2,1,3,D=1,2,3,R=(1,2),(2,3),(3,2),(1,3),图形结构,节点间的连结是任意的,1,数据的逻辑结构,2,、数据的存储结构,3,、数据的运算：检索、排序、插入、删除、修改等。,A,线性结构,B,非线性结构,A,顺序存储,B,链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(,亦称物理结构,),元素,n,.,元素,i,.,元素,2,元素,1,L,o,L,o,+m,L,o,+(i-1)*m,L,o,+,（,n-1)*m,存储地址,存储内容,Loc(a,)=L,o,+,（,i-1)*m,顺序存储,每个元素所占用,的存储单元个数,元素,n,.,元素,i,.,元素,2,元素,1,存储内容,顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。,顺序存储结构的三个弱点：,1.,作插入或删除操作时，需移动大量元数。,2.,长度变化较大时，需按最大空间分配。,3.,表的容量难以扩充。,1,数据的逻辑结构,2,、数据的存储结构,3,、数据的运算：检索、排序、插入、删除、修改等。,A,线性结构,B,非线性结构,A,顺序存储,B,链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(,亦称物理结构,),1536,元素,2,1400,元素,1,1346,元素,3,元素,4,1345,h,链式存储,每个节点都由两部分组成：,数据域,和,指针域,。,数据域,存放元素本身的数据，,指针域,存放指针。,数据元素之间逻辑上的联系由指针来体现,。,1536,元素,2,1400,元素,1,1346,元素,3,元素,4,head,1346,元素,3,1536,.,.,.,1536,元素,2,1400,.,.,.,元素,4,1346,1400,元素,1,1345,指针,存储内容,存储地址,链式存储,1345,1536,元素,2,1400,元素,1,1346,元素,3,元素,4,1345,h,链式存储,1.,比顺序存储结构的存储密度小,(,每个节点都由数据域和指针愈组成,),。,2.,逻辑上相邻的节点物理上不必相邻。,3.,插入、删除灵活,(,不必移动节点，只要改变节点中的指针,),。,链接存储结构特点：,1,数据的逻辑结构,2,、数据的存储结构,3,、,数据的运算,：检索、排序、插入、删除、修改等。,A,线性结构,B,非线性结构,A,顺序存储,B,链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(,亦称物理结构,),线性结构和非线性结构,如果一个非空的数据结构满足下列两个条件：,有且只有一个根结点；,每一个结点最多有一个前件，也最多有一个后件,则称该数据结构为线性结构（又称为线性表）。,一个线性结构中插入或删除任何一个节点后还应是线性结构。,如果一个数据结构不是线性结构，则称之为非线性结构。,线性与非线性结构都可以是空的数据结构。,1.3,线性表,(0.24%),1.3.1,线性表的定义,线性表是,n,个元素的有限序列，它们之间的关系可以排成一个线性序列：,a1,，,a2,，,，,ai,，,，,an,其中,n,称作表的长度，当,n=0,时，称作空表。,线性表的特点：,1.,线性表中所有元素的性质相同。,2.,除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继。第一个数据元素无前驱，最后一个数据元素无后继。,3.,数据元素在表中的位置只取决于它自身的序号。,在线性表上常用的运算有：,初始化、求长度、取元素、修改、插入、删除、检索、排序。,1.3.2,线性表的顺序存储结构及其插入与删除操作,特点：,1,、线性表中数据元素类型一致，只有数据域，存储空间利用率高。,2,、所有元素所占的存储空间是连续的,3,、各数据元素在存储空间中是按逻辑顺序依次存放的,2.,做插入、删除时需移动大量元素。,3.,空间估计不明时，按最大空间分配。,元素,a,n,.,元素,a,i,.,元素,a,2,元素,a,1,b,b+m,b+(i-1)*m,b+(maxlen-1)*m,存储地址,内存状态,Loc(,元素,i)=b+,（,i-1)*m,顺序存储结构示意图,(,顺序表,),：,首地址,起始地址,基地址,每个元素所占用,的存储单元个数,.,a,2,a,1,a,n,.,a,i+1,a,i,0,1,i-1,i,n-1,1-,1,插入运算,a,i-1,.,a,2,a,1,a,length,a,i+1,a,i,x,a,i-1,.,a,2,a,1,a,i,a,i+1,a,length,a,length,a,i+1,a,i,x,插入算法的分析,假设线性表中含有,n,个数据元素，在进行插入操作时，若假定在,n+1,个位置上插入元素的可能性均等，则平均移动元素的个数为：,删除算法的分析,在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：,分析结论,顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。,1.4,栈和队列,(3.47%),1.4.1,栈和队列的定义,栈和队列,是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为,限定性的数据结构,。,1.4.1.1,栈的定义,栈：,限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为,后进先出,设栈,s=,（,a,1,，,a,2,，,.,a,i,，,.,，,a,n,）,，,其中,a,1,是栈底元素，,a,n,是栈顶元素。,栈顶（,top),：允许插入和删除的一端；,约定,top,始终指向新数据元素将存放的位置。,栈底（,bottom):,不允许插入和删除的一端。,a,1,a,2,.,a,n,进栈,出栈,栈顶,栈底,队列的主要运算,（,1,）设置一个空队列；,（,2,）插入一个新的队尾元素，称为进队；,（,3,）删除队头元素，称为出队；,（,4,）读取队头元素；,1.4.1.2,队列的定义,定义：,一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表 。此种结构称为,先进先出（,FIFO,）表,。,a,1,a,2,a,3,a,4,a,n-1,a,n,队 列 示 意 图,队头,队尾,1.4.2,栈的顺序存储结构及其基本运算,a,2,a,1,a,1,a,2,top,用顺序存储结构表示的栈。,顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量,top,指示栈顶位置，,称为,栈,顶指针,，,它始终指向待插入元素的位置。,基本运算：,压（进）栈：,PUSH,出栈：,POP,3 2 1 0,(a),rear=front=-1(,队空）,e,3,e,4,(c),e1,e2,出队，,e4,入队,队 满,rear,front,e,1,e,2,e,3,(b),rear,front,(b)e1,e2,e3,入队,队空时，令,rear=front=-1,，,当有新元素入队时，尾指针加,1,，当有元素出队时，头指针加,1,。故在非空队列中，,头指针,始终指向,队头元素前一个位置,，而,尾指针,始终指向,队尾元素的位置,1.4.3,队列的顺序存储结构及其基本运算,1.5,线性链表（线性表的链式存储结构）,(0.24%),线性链表,循环链表,结构及其基本运算,1.5.1,线性表的链式存储结构,将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。,数据域存放数据，指针域存放,后继结点,的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。,上图的线性表为,ZHAO,，,QIAN,，,SUN,，,LI,，,ZHOU,，,WU,，,ZHENG,，,WANG,线性链表表示法,:,链式存储结构的特点,插入、删除灵活方便，不需要移动结点，只要改变结点中指针域的值即可。,适合于线性表是动态变化的,不进行频繁查找操作、但经常进行插入删除时使用。,链表的查找只能从头指针开始顺序查找。,1.5.2,循环链表,:,首尾相接的链表。,将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。,a,1,a,2,a,n,a,3,L,.,带头结点的单链表,a,1,a,2,a,n,a,3,L,.,循环单链表,1.5.3,双向链表,在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。,data,next,before,1.6,树与二叉树,(2.93%),树的基本概念,二叉树的定义及其存储结构,二叉树的前序、中序和后序遍历,1.6.1,树的定义,由一个或多个结点组成的有限集合,。,仅有一个根结点，结点间有明显的层次结构关系。,A,C,G,T,2,D,H,I,T,3,J,M,B,E,L,K,T,1,F,现实世界中，能用树的结构表示的例子：,学校的行政关系、书的层次结构、人类的家族血缘关系等。,介绍几个概念：,结点（,Node,）：树中的元素，包含数据项及若干指向其子树的分支。,结点的度（,Degree,）：结点拥有的子树数。,结点的层次：从根结点开始算起，根为第一层。,叶子（,Leaf,）：度为零的结点，也称端结点。,孩子（,Child,）：结点子树的根称为该结点的孩子结点。,兄弟（,Sibling,）：,同一双亲的孩子。,双亲（,Parent,）：孩子结点的上层结点，称为这些结点的双亲。,深度（,Depth),：树中结点的最大层次数。,森林（,Forest,）：,M,棵互不相交的树的集合。,A,C,G,T,2,D,H,I,T,3,J,M,B,E,L,K,T,1,F,1.6.2,二叉树（,Binary Tree,）,1,、二叉树的定义及其性质,(1),二叉树的定义,二叉树的五种基本形态,二叉树一种特殊的树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。,空二叉树,仅有,根结点,右子树为空,左子树为空,左右子树均非空,因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。,二叉数是,n(n,0),个结点的有限集合。它或为空数,(n=0),或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉数组成。,特别要注意：,二叉数不是,树的特殊情况。,a,a,b,b,两棵不同的二叉数,A,、,二叉树的第,i,层上至多有,2,i-1,（,i,1,）个结点。,(2),二叉树的基本性质,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,第三层上,(i=3),，有,2,3-1,=4,个节点。,第四层上,(i=4),，有,2,4-1,=8,个节点。,A,、,二叉树的第,i,层上至多有,2,i-1,（,i,1,）个结点。,B,、,深度为,h,的二叉树中至多含有,2,h,-1,个结点。,(2),二叉树的基本性质,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,此树的深度,h=4,，共有,2,4,-1=15,个节点。,A,、,二叉树的第,i,层上至多有,2,i-1,（,i,1,）个结点。,B,、,深度为,h,的二叉树中至多含有,2,h,-1,个结点。,C,、,若在任意一棵二叉树中，有,n,0,个叶子结点，,有,n,2,个度为,2,的结点，则：,n,0,=n,2,+1,(2),二叉树的基本性质,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,n,0,=8,n,2,=7,（,3,）满二叉树,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,特点：每一层上都含有最大结点数。,4,2,3,1,6,7,8,9,10,11,12,5,非完全二叉树,（,4,）完全二叉树,4,2,3,1,6,7,8,9,10,11,12,5,完全二叉树,特点：除最后一层外，每一层都取最大结点数，,最后一层结点都集中在该层最左边的若干位置。,（,5,）树与二叉树的区别,A,树的结点个数至少为,1,，而二叉树的结点个数可以为,0,。,B,树中结点的最大度数没有限制，二叉树结点最大度数为,2,。,C,树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。,树,二叉树,1.6.3,二叉树的遍历,查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。,（,1,）遍历定义及遍历算法,遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。,按先左后右的原则，一般使用三种遍历：,先序遍历,(D L R):,访问根结点，按先序遍历左子树，按先序遍历右子树。,中序遍历,(L D R):,按中序遍历左子树，访问根结点，按中序遍历右子树。,后序遍历,(L R D):,按后序遍历左子树，按后序遍历右子树，访问根结点。,二叉树为空时，执行空操作，即空二叉树已遍历完。,（,2,）遍历算法,先序遍历：,D L R,中序遍历：,L D R,后序遍历：,L R D,A,D,B,C,T,1,T,2,T,3,D L R,A,D L R,D L R,B,D,C,D L R,以先序遍历,D L R,为例演示遍历过程,ABDC,BDAC,DBCA,1.7,查找和排序,顺序查找与二分查找算法,基本排序算法（交换类排序、选择类排序、插入类排序）,1.7.1,查找,(0.89%),查找是在一个给定的数据结构中，,根据给定的条件查找满足条件的结点,。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。,查找的结果：,查找成功：,找到满足条件的结点,查找失败：,找不到满足条件的结点。,1.7.1.1,顺序查找（线性查找）,查找过程：,对给定的一关键字,K,，从线性表的一端开始，逐个进行记录的关键字和,K,的比较，直到找到关键字等于,K,的记录或到达表的另一端。,可以采用从前向后查，也可采用从后向前查的方法。,在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。,在下面两种情况下只能采取顺序查找：,a.,线性表为无序表（元素排列是无序的）；,b.,即使是有序线性表，但采用的是链式存储结构。,最坏比较,n,次。,2.7.1.2,折半查找（二分法查找）,思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。,前提：必须在,具有顺序存储结构的,有序表中进行,。,分三种情况：,1,）若中间项的值等于,x,则说明已查到。,2,）若,x,小于中间项的值，则在线性表的前半部分查找；,3,）若,x,大于中间项的值，则在线性表的后半部分查找。,特点,：比顺序查找方法效率高。最坏的情况下，需要比较,log2n,次,。,查找,23,和,79,的过程如下图：,mid=(low+high)/2,不进位取整,(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),low,high,mid,(08,14,23,37,46,55,68,79,91),low,high=mid-1,mid,(08,14,23,37,46,55,68,79,91),low=mid+1,high,mid,(08,14,23,37,46,55,68,79,91),low,high,mid,(08,14,23,37,46,55,68,79,91),low,high,mid,(08,14,23,37,46,55,68,79,91),low,high,mid,1.7.2,排序,(0.6%),1.7.2.1,概述,1,、排序的功能：,将一个数据元素（或记录）的,任意序列,，重新排成一个按关键字,有序,的序列。,2,、排序过程的组成步骤：,首先,比较,两个关键字的大小；,然后将记录从一个位置,移动,到另一个位置。,排序方法,插入排序,选择排序,交换排序,简单插入排序,希尔排序,简单选择排序,堆排序,冒泡排序,快速排序,1.7.2.2,插入排序,简单插入、希尔,1,、简单插入排序,:,基本思想：从数组的第,2,号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上。,最坏情况需要,n(n-1)/2,次比较,该算法适合于,n,较小的情况，时间复杂度为,O(n,2,).,待排元素序列,：,53,27 36 15 69 42,第一次排序：,27 53,36 15 69 42,第二次排序：,27 36 53,15 69 42,第三次排序：,15 27 36 53,69 42,第四次排序：,15 27 36 53 69,42,第五次排序：,15 27 36 42 53 69,直接插入排序示例,对于有,n,个数据元素的待排序列，插入操作要进行,n-1,次,2,、希尔排序,书,43,页图,1.39,比较次数为,O(n1.5),1,、简单选择排序,思想：首先从,1n,个元素中选出关键字,最小,的记录交换到,第一个,位置上。然后再从第,2,个到第,n,个元素中选出次小的记录交换到,第二个,位置上，依次类推。,时间复杂度为,O(n,2,),，最坏情况下需要比较,n(n-1)/2,次,适用于,待排序元素较少,的情况。,1.7.2.3,选择排序,简单选择排序、堆排序,初态,8,3 9 1 6,8,3 9 1 6,8,3 9 1 6,8,3 9 1 6,i,j,k,i,j,k,i,j,k,i,j,k,1,3,9 8 6,互换,i,j,k,1,3,9 8 6,i,k,j,1,3,9 8 6,i,k,j,第一趟,第二趟,1,3,9,8 6,i,k,j,第三趟,2,堆排序,也是一种选择排序。是具有特定条件的顺序存储的完全二叉树，其特定条件是：,任何一个非叶子结点的关键字大于等于（或小于等于）子女的关键字的值。,(1),堆的示例,89,76,24,33,15,10,11,25,36,49,78,56,(a):,堆顶元素取最大值,(b):,堆顶元素取最小值,(2),实现堆排序需解决两个问题：,（,1,）如何由一个无序序列建成一个堆？,（,2,）输出堆顶元素后，如何将剩余元素调整成一个新的堆？,堆排序需要比较的次数为,O(nlog,2,n),1.7.2.4,交 换 排 序,交换排序的特点在于,交换,。有冒泡和快速排序两种。,1,、冒泡排序（起泡排序）,思想：,小的浮起，大的沉底。,从左端开始比较。,第一趟：第,1,个与第,2,个比较，大则交换；第,2,个与第,3,个比较，,大则交换，,关键字最大的记录交换到最后一个位置上；,第二趟：对前,n-1,个记录进行同样的操作，关键字次大的记录交换,到第,n-1,个,位置上；,依次类推，则完成排序。,正序：时间复杂度为,O(n,),逆序：时间复杂度为,O(n,2,),适合于数据较少的情况。,排序,n,个记录的文件最多需要,n-1,趟冒泡排序。,第,六,趟,排,序,后,第,五,趟,排,序,后,第,四,趟,排,序,后,第,三,趟,排,序,后,第,二,趟,排,序,后,第,一,趟,排,序,后,初,始,关,键,字,思想：小的浮起，大的沉底。,49,36,41,65,11,78,36,65,36,41,56,36,41,65,41,36,41,56,11,78,36,36,41,49,11,56,49,25,25,25,11,49,49,56,11,11,11,25,25,25,25,2,、快速排序,(,对冒泡排序的改进）,思想：通过一趟排序将待排序列,分成两部分,，使其中,一部分记录,的关键字均比,另一部分小,，再分别对这两部分排序，以达到整个序列有序。,关键字通常取第一个记录的值为基准值。,做法：,附设两个指针,low,和,high,，初值分别指向,第一个记录,和,最后一个记录,，设关键字为,key,，首先从,high,所指位置起,向前,搜索，找到第一个,小于,基准值的记录与基准记录交换，然后从,low,所指位置起,向后,搜索，找到第一个,大于,基准值的记录与基准记录交换，重复这两步直至,low=high,为止。,时间复杂度：,O(log,2,n),最坏：,n(n-1)/2,快速排序过程示意图：,有序序列,6 18 23 52 67,key,初始序列,23 52 6 67 18,low,high,一次交换,18 52 6 67 23,low,high,二次交换,18 23 6 67 52,high,三次交换,18 6 23 67 52,/,完成一趟排序后分别进行快速排序,low,high,1.7.2.5,内部排序方法的选择,各种排序方法各有优缺点，故在不同情况下可作不同的选择。通常需考虑的因素有,：,待排序的记录个数；记录本身的大小；记录的键值分布情况,等。,若待排序的记录个数,n,较小时，可采用简单排序方法。,若,n,较大时，应采用快速排序或堆排序。,若待排序的记录已基本有序，可采用起泡排序。,