计算机考研基础讲义数据结构基础

数据结构基础,计算机考研小组(100),2010年计算机考研基础班讲义,第一章绪论,什么是数据结构,直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间关系和运算的一门学科。数据结构是指数据之间的关系按某种关系组织起来的一批数据。以一定的存储方式把它们存储到计算机的存储器中，并在这些数据上定义一个运算集合，这就是数据结构。,学习数据结构的重要性,“数据结构”在计算机科学中是一门综合性的专业基础课,在考研中占很大的分值。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。,1.2数据结构的概念,一、基本概念数据：能输入计算机且被能计算机处理的一切对象。数据元素：对现实世界中某独立个体的数据描述。数据项：具有独立意义的最小数据单位。数据类型：每个数据项必须属于某确定的数据类型。,基础,1.3数据的逻辑结构,一、基本概念数据对象：具有相同特征的数据元素的集合。关系：在数据对象中各数据元素之间存在着某种关系（或联系）。这种关系反映了该数据对象中数据元素所固有的一种结构。在数据处理领域，通常把数据之间这种固有的关系简单的用前驱和后继关系描述。,1.3数据的逻辑结构,二、数据的逻辑结构设D表示数据元素的集合，R表示D上的关系的集合，则一个数据结构B可表示为：B=（D，R）由此可见数据结构由两部分构成（1）表示各元素的信息D（2）表示数据之间关系的信息R一般用二元组表示D中各数据元素之间的前驱、后继关系。假设a,b是D中的两个元素，则二元组表示a是b的前驱，b是a的后继。,1.3数据的逻辑结构,三、数据结构的分类线性结构：除了一个根结点外，其他各结点有唯一的前驱；除了一个终端结点外，其他各结点有唯一的后继。树状结构：除了一个根结点外，各结点有唯一的前驱；所有的结点都可以有多个后继。网状结构：各结点可以有多个前驱或多个后继。,1.4数据的存储结构,数据结构在计算机中的表示称为数据的存储结构。数据结构包括结点的值及结点之间的关系，其存储结构除了必须存储结点的值外，还得能以直接或隐含的方式体现出结点之间的关系。四种基本的存储方式：1、顺序方式顺序结构最适合于线性结构，它把逻辑上相邻的结点存放到物理上相邻的存储单元中，顺序存储结构只存储结点的值，不存储结点的关系，结点的关系通过存储单元相邻关系隐含表示出来。,1.4数据的存储结构,2、链接方式链接存储方式不仅存储结点的值，而且还存储结点之间的关系。它利用结点附加的指针字段，存储其后继结点的地址。3、索引方式在线性结构中，各结点可以依前驱、后继关系排成一个序列（a1,a2,a3,an)。每个结点ai在序列中都对应一个序号i序号i也称为结点ai的索引号。索引存储就是通过建立一个附加的索引表，然后利用索引表中的索引项的值来确定结点的实际存储单元的地址。,1.4数据的存储结构,4、散列方式利用该结点的值确定该结点的存储单元地址。,1.5数据运算和算法,1、数据运算按一定的逻辑结构把数据组织起来，采用适当的存储方式把数据结构存储到计算机中，最终的目的是为了有效地处理数据，提高数据的运算效率。1）插入：往数据结构中添加新的结点称为插入。2）删除：把指定的结点从数据结构中删除。3）更新：改变指定结点的值或者改变某些结点的关系称为更新。4）查找：在数据结构中查找某些满足条件的结点。5）排序：对线性表的各结点，按指定数据项的值从小到大或从大到小的重新排列。排序运算实际上是破坏线性表的旧关系，重新建立线性表的新关系。,1.5数据运算和算法,2、算法算法是对特定问题求解步骤的一种描述。算法应具有的几个特征：1）有穷性：算法应在计算机存储资源容许的条件下，在一定时间内执行完毕。2）确定性：算法的每一步骤应定义明确，没有二义。3）可行性：算法是可以被计算机执行的。当输入正确的数据后，应得到正确的结果。,1.5数据运算和算法,3、算法的评价对算法评价的几个指标空间复杂度空间复杂度是指执行算法所需要的辅助空间大小。时间复杂度时间复杂度是指执行完算法所需的运算次数。,第二章线性表,线性表是一种最简单、最常用的数据结构。线性表的主要存储结构有两种：顺序存储结构和链接存储结构。,2.1线性表的定义及基本运算,一、线性表的定义线性表是由n(n0)个性质相同的数据元素a1,a2,a3,an组成的有限序列，记为(a1,a2,a3,an)。二、线性表的基本运算（1）置线性表为空表；（2）求线性表的长度；（3）读取线性表中的第i个元素；（4）修改线性表中的第i个元素；（5）查找线性表中具有某个特征值的数据元素；,2.1线性表的定义及基本运算,二、线性表的基本运算（6）在线性表的第i个数据元素之前或之后插入一个新的数据元素；（7）删除线性表中第i个数据元素或满足给定条件的第一个数据元素；（8）对线性表中的所有元素按照给定的关键字大小进行排序。,2.2线性表的顺序存储结构及运算,一、线性表的顺序存储结构线性表的顺序存储结构是将线性表中的结点按其逻辑顺序依次存放在内存中一组连续的存储单元中，即把线性表中相邻的结点存放在地址相邻的内存单元中。线性表在c语言中用一维数组表示。c语言的描述TypedefintET;#definemaxlen1000ETsmaxlen;,2.2线性表的顺序存储结构及运算,一、线性表的顺序存储结构线性表C语言描述的说明：在C语言中，数组的下标是从0开始的，数据结构中的结点的序号是从一开始的。因此在线性表中的第一个元素是指S0。两个相邻结点ai和ai+1的存储位置记为LOC（ai）和LOC（ai+1），则结点满足以下关系LOC（ai+1）=LOC（ai）+1,2.2线性表的顺序存储结构及运算,二、线性表的运算1、插入运算的算法描述：intinsertqlist(inti,ETx,ETs,int*np)intj,n;n=*np;if(in+1)return(0);elsefor(j=n;j=i;j-)sj=sj-1;sj=x;*np=+n;return(1);,2.2线性表的顺序存储结构及运算,二、线性表的运算2、删除运算的算法描述：intdelqlist(inti,ETs,int*np)intj,n;n=*np;if(in)return(0);elsefor(j=i;jlink=NULL;head=p;for(i=1;idata);q-link=NULL;p-link=q;p=p-link;return(head);,2.3线性表的链接存储结构及运算,2、查找链表中的X查找链表中是否存在结点X，算法的基本思想为：从表头指针指向的第一个结点开始，依次把表中结点的数据域和给定值X进行比较，直到某个结点的数据域的值等于给定值X（既查找成功），则返回该结点的地址；如果查找到表尾仍未找到（既查找失败），则返回NULL。,查找单链表中结点X的算法描述：NODE*found(NODE*head,ETx)NODE*p;p=head-link;while(p!=NULL),2.3线性表的链接存储结构及运算,3、在单链表中插入新结点X在链表中的某一结点p之后插入一个数据为X的新结点。过程如下：（1）生成一个新结点q，将X赋给q-data;（2）修改有关结点的指针域：将原p结点的后继作为q结点的后继，q结点作为p结点的后继。,在单链表中插入新结点X的算法描述：voidinsert(NODE*head,NODE*p,ETx)NODE*q;q=(NODE*)malloc(sizeof(NODE);q-data=x;if(head-link=NULL)head-link=q;q-link=NULL;elseq-link=p-link;p-link=q;,2.3线性表的链接存储结构及运算,4、删除单链表中的结点X删除单链表中的结点X，并由系统收回其占用的存储空间。过程如下：（1）设定两指针p和q，p指针指向被删除结点；q为跟踪结点，指向被删除结点的前驱结点;（2）p从表头指针head指向的第一个结点开始向后依次进行搜索。当p-data等于X时，被删除结点找到。（3）修改p的前驱结点q的指针域：使被删除结点的后继结点成为其前驱结点的后继结点，既q-link=p-link，p结点被删除，然后再释放存储空间。,在单链表中删除结点X的算法描述：voiddelete(NODE*head,ETx)NODE*p,*q;p=head;q=p;p=p-link;while(p!=NULL),2.3线性表的链接存储结构及运算,三、循环链表链表中的最后一个结点的指针指向链表中第一个结点，使链表形成一个环行，此链表称循环链表。循环链表是线性链表的一种变形。其优点是从链表中任何一个结点出发都可以访问到表中的所有结点。在循环链表中为了使空表和非空表处理一致，可以附加一个表头结点。,2.3线性表的链接存储结构及运算,三、循环链表,非空表（a),head,head,空表（b),(1)在头指针为head的循环链表查找值为x的前驱结点。NODE*looknode(head,x)ETx;NODE*head;NODE*p;p=head;while(p-link!=head),(2)在头指针为head的循环链表在值为x的结点之前插入一个值为b的新结点。NODEinsnode(head,x,b)ETx,b;NODE*head;NODE*p,*q;p=(NODE*)malloc(sizeof(NODE);p-data=b;q=looknode(head,x);p-link=q-link;q-link=p;return;,(3)在头指针为head的循环链表中，删除值为x的结点。Voiddelnode(head,x)ETx;NODE*head;NODE*p,*q;q=looknode(head,x);if(q-link=head)printf(“Nothisnodethelist!n”)return;p=q-link;q-link=p-link;free(p);return;,2.3线性表的链接存储结构及运算,四、循环链表一个链表的每一个结点含有两个指针域，一个指针指向其前驱结点，另一个指针指向其后继结点，这样的链表称为双向链表。,五、双向链表,head,llink,rlink,data,带头结点的双向链表,双向链表的结点结构,2.4数组,一、数组的定义数组是由一组类型相同的数据元素构造而成。若数组元素只含有一个下标，这样的数组称为一维数组。当一个数组的每一个数组元素都含有两个下标时，该数组称为两维数组。,2.4数组,二、数组的存储结构数组是一种顺序存储结构。也就是将数组元素顺序地存放在一片连续的存储单元中。三、规则矩阵的压缩存储有时矩阵中包含大量的零元素（或某一确定值的元素），为了节省存储空间，可以对这类矩阵采用压缩存储。所谓压缩存储是指对零元素不分配存储空间，而只对非零元素进行存储。压缩存储必须能够体现矩阵的逻辑结构。,2.4数组,四、稀疏矩阵及存储当一个矩阵的非零元素的个数远远少于零元素的个数时，称该矩阵为稀疏矩阵。对稀疏矩阵的存储方式常采用压缩存储。方法有两种：三元组表和十字链表。1、在稀疏矩阵中，每一个非零元素可以用它所在的行号i、列号j以及元素值aij组成的三元组(i,j,aij)来表示。三元组的结点定义：typedefstructnodeintr,c;ETv;NODE;,2.4数组,00100020000000000700050,rcv,Ma0,Ma1,Ma2,Ma3,Ma4,Ma5,Ma6,A=,2.4数组,090000000020001000500070,rcv,Mb0,Mb1,Mb2,Mb3,Mb4,Mb5,Mb6,B=,2.4数组,实现矩阵转置的算法：intsyz(NODEma,NODEmb)inti,j,n,t,k;if(ma0.v=0)return(0);n=ma0.c;t=ma0.v;mb0.r=n;mb0.c=ma0.r;mb0.v=t;k=1;for(j=1;jlink=top;top=p;return(top);,3.1.2栈的存储结构及其运算,(2)出栈栈顶元素出栈算法的C语言描述：NODE*popstack(NODE*top,ET*p)NODE*q;if(top!=NULL)*q=top;*p=top-data;top=top-link;free(q);return(top);,3.1.2栈的存储结构及其运算,3、栈的应用举例表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。(1)中缀算术表达式：将运算符置于两个操作数中间的算术表达式，称中缀表达史。（2）后缀表达式：将运算符置于两个操作数的后面的算术表达式称为后缀表达式。这种表达式不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行。计算机在处理这种表达式时，只需对其扫描一遍，就可完成计算。,3.2队列,在日常生活中队列很常见，如，我们经常排队购物或购票，排队是体现了“先来先服务”（即“先进先出”）的原则。队列在计算机系统中的应用也非常广泛。例如：操作系统中的作业排队。在多道程序运行的计算机系统中，可以同时有多个作业运行，它们的运算结果都需要通过通道输出，若通道尚未完成输出，则后来的作业应排队等待，每当通道完成输出时，则从队列的队头退出作业的输出操作，而凡是申请该通道输出的作业都从队尾进入该队列。,3.2队列,计算机系统中输入输出缓冲区的结构也是队列的应用。在计算机系统中经常会遇到两个设备之间的数据传输，不同的设备通常处理数据的速度是不同的，当需要在它们之间连续处理一批数据时，高速设备总是要等待低速设备，这就造成计算机处理效率的大大降低。为了解决这一速度不匹配的矛盾，通常就是在这两个设备之间设置一个缓冲区。这样，高速设备就不必每次等待低速设备处理完一个数据，而是把要处理的数据依次从一端加入缓冲区，而低速设备从另一端取走要处理的数据。,3.2队列,一、队列的定义及运算队列也是一种特殊的线性表，它是只允许在表的一端进行插入，在表的另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队首。若给定队列q=(a0,a1,a2,a3,a4,an-1)，我们称a0是队首元素，an-1是队尾元素。,a0,a1,a2,a3,a4,aian-1,出队,入队,第四章递归,递归是程序设计中一个重要的算法设计方法和技术。递归子程序是通过调用自身来完成与自身要求相同的子问题的求解,并利用系统内部功能自动实现调用过程中信息的保存与恢复，而省略了程序设计中的许多细节操作，简化了程序设计过程,使程序设计人员可以集中注意力于主要问题求解上。,4.1递归的定义,递归就是一个事件或对象部分由自己组成。递归算法包括递推和回归两部分（1）递推：就是为得到问题的解，将其推倒比原来问题简单的问题的求解。（2）就是指当“简单的问题得到解后，回归到原问题的解上。,4.2递归的实现,1、采用递归算法具备的条件（1）所需解决的问题可以转化成另一个问题，而解决新问题的方法与原始问题的解法相同。（2）必须具备终止递归的条件。程序中不能出现无终止的递归调用，而只能出现有限次的，有终止的递归调用。,4.2递归的实现,2、递归算法示例:n！（阶乘）算法的求解。intfact(intn)if(n=0)s=1;return1;elses=n*fact(n-1);returns;voidmain()intn;n=fact(5);printf(“n=%dn”,n,4.3阶乘递归的实现,活动记录进退栈示意图,s=fact(1)=1*fact(0)=1,s=fact(2)=2*fact(1)=2,s=fact(3)=3*fact(2)=6,s=fact(4)=4*fact(3)=24,s=fact(5)=5*fact(4)=120,fact(0)=1,调用者,递归调用过程示意图从图中可看到fact函数共被调用5次，即fact(5)、fact(4)、fact(3)、fact(2)、fact(1)。其中，fact(5)为主函数调用，其它则为在fact函数内调用。每一次递归调用并未立即得到结果，而是进一步向深度递归调用，直到n=1或n=0时，函数fact结果为1，然后再一一返回计算，最终得到结果。,例汉诺塔传说在创世纪时，在一个叫Brahma的寺庙里，有三个柱子，其中一柱上有64个盘子从小到大依次叠放，僧侣的工作是将这64个盘子从一根柱子移到另一个柱子上。移动时的规则：每次只能移动一个盘子；只能小盘子在大盘子上面；可以使用任一柱子。当工作做完之后，就标志着世界永远和平。,n,n1,分析：设三根柱子分别为x，y,z,盘子在x柱上，要移到z柱上。1、当n=1时，盘子直接从x柱移到z柱上；2、当n1时,则设法将前n1个盘子借助z，从x移到y柱上，把盘子n从x移到z柱上；把n1个盘子从y移到z柱上。,Hanoi问题,voidHanoi(intn,charx,chary,charz)/将n个编号从上到下为1n的盘子从x柱，借助y柱移到z柱if(n=1)move(x,1,z);/将编号为1的盘子从x柱移到z柱else/将n-1个编号从上到下为1n-1的盘子从x柱，借助y柱移到z柱Hanoi(n-1,x,z,y);move(x,n,z);/将编号为n的盘子从x柱移到z柱/将n-1个编号从上到下为1n-1的盘子从y柱，借助x柱移到z柱Hanoi(n-1,y,x,z);/Hanoi,第五章串,在计算机的各方面应用中，非数值处理问题的应用越来越多。如程序源代码，在事务处理系统中，用户的姓名和地址及货物的名称、规格等，都是作为一种字符串数据进行处理的。字符串一般简称为串，可以将它看作是一种特殊的线性表，这种线性表的数据元素的类型总是字符型的，字符串的数据对象约束为字符集。在一般线性表的基本操作中，大多以“单个元素”作为操作对象，而在串中，则是以“串的整体”或一部分作为操作对象。因此，一般线性表和串的操作有很大的不同。本章主要讨论串的基本概念、存储结构和一些基本的串处理操作。,5.1串的基本概念,串（或字符串）（String）是由零个或多个字符组成的有限序列。一般记作s=a0a1a2an-1(n0)其中：s为串名，用双引号括起来的字符序列是串的值；ai(0in-1)可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；字符串字符的数目n称为串的长度。零个字符的串称为空串，通常以两个相邻的双引号来表示空串（Nullstring），如：s=，它的长度为零；仅由空格组成的的串称为空格串，如：s=；若串中含有空格，在计算串长时，空格应计入串的长度中，如：s=Imastudent的长度为13。,5.2串的存储结构,一、顺序存储和线性表一样，可以用一组连续的存储单元依次存放串中各字符。利用字符单元地址的顺序表示串中字符的相邻关系。structstringcharch_stringmaxlen;intlen;当计算机按字(Word)为单位编址时，一个存储单元由若干字节组成。这时，顺序存储结构有紧凑格式和非紧凑格式两种。,5.3串的基本运算,串的基本运算有赋值、串连接、求串长、取子串、子串定位、判断两个串是否相等、插入子串，删除子串等。在本节中，我们尽可能以C语言的库函数表示其中的一些运算，若没有库函数，则用自定义函数说明。structstringcharch_stringmaxlen;intlen;,1、串连接所谓串连接就是把一个串连接在另一个串的末尾，组成一个新串。,Structstringconcat(s1,s2)structstrings1,s2;structstrings;inti;if(s1.len+s2.len=maxlen)for(i=0;is1.len;i+)s.ch_stringi=s1.ch_stringi;for(i=0;is2.len;i+)s.ch_strings1.len+i=s2.ch_stringi;s.len=s1.len+s2.len;elses.len=0;return(s);,2、串相等判断当两个串的长度相等且各对应位置上的字符都相等时，两个字符串才相等。,intequal(s1,s2)structstrings1,s2;inti;if(s1.len!=s2.len)return(0);elsefor(i=0;i=1),4、插入子串所谓插入子串就是在指定位置上插入一个子串。,structstringinsert(s,s1,n)structstrings,s1;intn;structstringsub1,sub2,str;if(s.len+s1.len=1),5、子串定位所谓子串定位就是给出子串在母串中的位置。子串的定位操作也称模式匹配。,intindex(s,s1)structstrings,s1;inti,j,k;i=0;while(i=s.lens1.len)j=i;k=0;while(k0)个结点的有穷集合K，且在K中定义了一个关系N，N满足以下条件：(1)有且仅有一个结点K0它对于关系N来说没有前驱，称K0为树的根结点；(2)除K0外，K中的每一个结点对于关系N来说有且仅有一个前驱；(3)K中各结点对关系N来说可以有m个后继,7.2树的常用术语,树的结点：包含一个数据元素及若干指向其子树的分支结点的度：结点所拥有的子树的个数称为该结点的度叶子：度为零的结点，又称终端结点树的深度：树中各结点层次的最大值称为该树的深度,7.3二叉树,二叉数的定义二叉数的存储结构：顺序存储结构、链式存储结构二叉数的遍历：就是按某一种规则访问树中的每一个结点，且使得每个结点均被访问一次，而且仅被访问一次。二叉数的遍历方法：前序遍历、中序遍历、后序遍历,第九章查找,查找(Searching)又称检索。就是从一个数据元素集合中找出某个特定的数据元素；它是数据处理中经常使用的一种重要的操作，尤其是当所涉及的数据量较大时，查找算法的优劣对整个软件的效率影响很大；本章首先介绍关于查找的基本概念，然后讨论查找的各种方法，最后对各种查找方法作一比较。,9.1查找的基本概念,查找表(SearchTable)是由同一类型的数据元素(或记录)构成的集合对查找表进行的操作有以下四种(1)查询某个特定的数据元素是否在查找表中(2)检索某个特定的数据元素的各种属性(3)在查找表中插入一个数据元素(4)从查找表中删除某个数据元素,9.1查找的基本概念,静态查找表(StaticSearchTable)若只对查找表进行查找和检索两种操作,则称此查找表为静态查找表动态查找表(DynamicSearchtable)若再查找过程中同时插入查找表中不存在的记录,或从查找表中删除已存在的某个记录,则称此类表为动态查找表关键字(Key)标志数据元素(或记录)中某个数据项的值,用它可以标识一个数据元素(或记录),9.2线性表的查找,顺序查找(sequentialSearch)也称线性查找,是一种最简单的查找方法,它属于静态查找顺序查找方法顺序查找的基本思想:从表的一端开始,顺序扫描线性表,依次用待查找的关键字值与线性表里各结点的关键字值逐个比较,若在表中找到了某个记录的关键字与待查找的关键字值相等,表明查找成功;如果找遍所有结点也没有与待查找的关键字值相等,则表明查找失败,9.2线性表的查找,main()inta100=0,12,5,36,58,21,61,15,16,32,17;inti,key;printf(InputtheKey:);scanf(%d,9.2线性表的查找,折半查找(binarySearch)也称为二分查找,是一种效率较高的查找方法,查找时要求表中的结点按关键字的大小排序折半查找方法折半查找的基本思想:首先用要查找的关键字值与中间位置结点的关键字值相比较(这个中间结点把线性表分成了两个子表).比较结果相等,则查找成功;若不相等,再根据要查找的关键字值与该中间结点关键字值的大小确定下一步查找在哪个子表中进行,#includemain()inta100=0,5,13,19,22,37,56,64,75,80,88,92;intlow=1,high=11,mid,key,flag=0;printf(InputtheKey:);scanf(%d,第十章排序,排序是在数据处理中经常使用的一种重要的算法。如何进行排序，特别是高效率的排序是计算机应用中的重要课题。排序的目的：是方便查找排序分为：内部排序、外部排序本章主要介绍几种常用的内部排序方法：插入排序、选择排序、交换排序的基本思想、排序步骤及实现方法,10.1排序的基本概念,关键字(Key)标志数据元素(或记录)中某个数据项的值,用它可以标识一个数据元素(或记录)排序(Sorting)是将一组记录按照记录中某个关键字进行有序（递增或递减）排列过程,10.2内部排序,插入排序插入排序就是按关键字大小将一个记录插入到一个有序的文件中的适当位置，并且插入后使文件仍然有序。直接插入排序每一趟将一个待排序的记录，按关键字的大小插入到已经排序的部分文件中适当位置，直到全部插入完成,main()inta100=0,19,1,23,17,19,55,84,15;inti,j;for(i=2;i=8;+i)if(aiai-1)a0=ai;for(j=i-1;a0aj;-j)aj+1=aj;aj+1=a0;for(i=1;i=8;i+)printf(%d,ai);printf(n);,10.2内部排序,折半插入排序由于插入排序的基本操作是在一个有序表中进行查找和插入，而查找操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排列（BinaryInsertionSort），又称为二分法插入排序。,main()inta100=0,19,1,23,17,19,55,84,15;inti,j,low,high,m;for(i=2;i=high+1;-j)aj+1=aj;ahigh+1=a0;for(i=1;ir2.key则交换r1和r2记录序列中的位置，否则不交换，然后再接着对当前序列中的第二个和第三个记录作同样的比较，依次类推，直到序列中最后两个记录处理完为止。,main()inta100=0,5,7,3,8,2,9,1,4;inti,j,flag,temp;flag=1;for(i=1;iaj+1)flag=1;temp=aj;aj=aj+1;aj+1=temp;for(i=1;i=8;i+)printf(%d,ai);printf(n);,10.2内部排序,快速排序快速排序是由冒泡排序改进而得的，是一种分区交换排序方法排序的基本思想：一趟快速