数据结构知识点全面总结.docx

《数据结构知识点全面总结.docx》由会员分享，可在线阅读，更多相关《数据结构知识点全面总结.docx（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章绪论内容提要：数据结构研究的内容。操作对象以及它们之间的关系和操作。针对非数值计算的程序设计问题，研究计算机的 数据结构涵盖的内容：钱进结构（建性表、栈、务太、串、数纽非线性结掏树结构图结构数据结构鞭疼结构遂式结构紊引结构散列结构耻除运翳数据运算）修改运算查找运算 排序运算基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。数据一一所有能被计算机识别、 存储和处理的符号的集合。数据元素一一是数据的基本单位，具有完整确定的实际意义。数据对象一一具有相同性质的数据元素的集合，是数据的一个子集。数据结构一一是相互之间存在一种或多种特定关系的数据元素的集合，表示为：Data_S

2、tructure= （ D, R）数据类型一一是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型一一由用户定义的一个数学模型与定义在该模型上的一组操作， 它由基本的数据类型构成。算法的定义及五个特征。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。算法的基本特性：输入、输出、有穷性、确定性、可行性算法设计要求。 正确性、可读性、健壮性、效率与低存储量需求算法分析。时间复杂度、空间复杂度、稳定性学习重点：数据结构的“三要素”：逻辑结构、物理（存储）结构 及在这种结构上所定义的操作（运算）。用计算语句频度来估算算法的时间复杂度。循环队列：队空条件：

3、front = rear(初始化时 front = rear)队满条件：front = (rear+1) % N(N=maxsize)队列长度(即数据元素个数)：L=( N+ rear- front) % N1)初始化一个空队列Status InitQueue ( Sueue &q ) / 初始化空循环队列q(q . base=(QEIemType *)malloc(sizeof(QEIemType)* QUEUE_MAXSIZE);/ 分配空间if (Iq.base) exit(OVERFLOW);/内存分配失败，退出程序q.front =q.rear=0; / 置空队歹 Ureturn O

4、K; /Ini tQueue;2)入队操作Status En Queue(Sueue &q, QEIemType e)向循环队列q的队尾加入一个元素eif (q.rear+1)% QUEUE_MAXSIZE = = q.fro nt)return ERROR ; 队满则上溢，无法再入队q.rear = ( q . rear + 1 )% QUEUE_MAXSIZE;q.base q.rear = e;新元素 e 入队return OK;/ En Queue;3)出队操作Status DeQueue ( Sueue &q, QEIemType &e)若队列不空，删除循环队列q的队头元素，由e返回

5、其值，并返回0Kif ( q.front = = q.rear) return ERROR;/ 队列空q.fron t=(q.fro nt+1) % QUEUE_MAXSIZE ;e = q.base q.front ;return OK;/ DeQueue链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加和设标记两种方法。1等于队头补充重点：1 .为什么要设计堆栈？它有什么独特用途？调用函数或子程序非它莫属； 递归运算的有力工具； 用于保护现场和恢复现场； 简化了程序设计的问题。2 .为什么要设计队列？它有什么独特用途？ 离散事件的模拟（模拟事件发生的先后顺序，例如CPU芯片

6、中的指令译码队列）； 操作系统中的作业调度（一个CPU执行多个作业）； 简化程序设计。3 .什么叫“假溢出”？如何解决？答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。解决假溢出的途径采用循环队列。4 .在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中IW 除一个元素时，其操作是先移动队首位置，后取出元素。5 .线性表、栈、队的异同点：相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。不同点：运算规则不同： 线性表为随机存取

7、； 而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO ;队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度 和简化设计等。第四章串内容提要：串是数据元素为字符的线性表，串的定义及操作。串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。串比较：int strcmp(char *s1 ,char *s2);求串长：int strle n( char *s);串连接：char strcat(char *to,char *from) 子串

8、T 定位：char strchr(char *s,char *c);串的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小”的问题。模式匹配算法。串有三种机内表示方法：耐一一用一组地址连续的存储单元存储串垃的字存诸称序列，属ifr态存储方式.堆令少存储表示-用-组连续的存储单元存储串垃的字符序列，但存瞎空同是在程序执祎过程中彩吉 分配而得* 鹫善串的块雒捽储表示仔临链式方式存储模式匹配算法：算法目的：确定主串中所含子串第一次出现的位置(定位)定位问题称为串的模式匹配，典型函数为In dex(S,T,pos)BF算法的实现一即编写 lndex(S, T, pos)函数BF算法设计思想：将

9、主串S的第pos个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串S的下一字符(pos+1)起，重新与T第一个字符比较。直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值 0。Int In dex_BP(SStri ng S, SStri ng T, i nt pos)返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0.其中，T 非空，1 posw StrLength(S)i=pos; j=1;while (i=S0 & jf(jTO) return i-T0;/T 子串指针

10、正常到尾，说明匹配成功，else return 0;/否则属于iS情况，i先到尾就不正常 /I ndex_BP补充重点：1 空串和空白串有无区别？答：有区别。空串(Null String)是指长度为零的串；而空白串(Blank String),是指包含一个或多个空白字符(空格键)的字符串2 .“空串是任意串的子串；任意串S都是S本身的子串,S本身外，S的其他子串称为S的真子串。f运建吉枪s =* uijua*定长顺序存储结构串T有储留吾构-堆存情结构二若干函数的实现1模式匹配算法模式匹配即子串定位运算即如何实现lDd1时，其余的结点分为 m （m 0）个互不相交的有限集合T1,T2 , , ,

11、 Tm。每个集合本身又是棵树，被称作这个根的子树。二叉树：是n （n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树 组成。术语：P88 二叉树的性质，存储结构。性质1:在二叉树的第i层上至多有2i1个结点（i0 ）。性质2：深度为k的二叉树至多有2k个结点（k0 ）。性质3：对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2 + 1性质4：具有n个结点的完全二叉树的深度必为性质5：对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号为2i + 1 ；其双亲的编号必为i/2 （i= 1时为根，除外）

12、。二叉树的存储结构：一、顺序存储结构按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。若是完全/满二叉树则可以做到唯一复 原。不是完全二叉树：一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。缺点：浪费空间；插入、删除不便二、链式存储结构用二叉链表即可方便表示。一般从根结点开始存储。irlt Cbtdngbt (hldd优点：不浪费空间；插入、删除方便 二叉树的遍历。指按照某种次序访问二叉树的所有结点，并且每个结点仅访问一次，得到一个线性序列。遍历规则二叉树由根、左子树、右子树构成，定义为D、 L、R若限定先左后右，则有三种实现方案：中序遍历后序遍历

13、DLRLDR LRD先序遍历树的存储结构，树、森林的遍历及和二叉树的相互转换。回顾2 :二叉树怎样还原为树？要点：逆操作，把所有右孩子变为兄弟！讨论1 :森林如何转为二叉树？法一：各森林先各自转为二叉树；依次连到前一个二叉树的右子树上。法二：森林直接变兄弟，再转为二叉树讨论2 :二叉树如何还原为森林？要点：把最右边的子树变为森林，其余右子树变为兄弟树和森林的存储方式：树有三种常用存储方式：双亲表示法孩子表示法孩子一兄弟表示法问：树t二叉树的“连线一抹线一旋转”如何由计算机自动实现？答：用“左孩子右兄弟”表示法来存储即可。存储的过程就是树转换为二叉树的过程！树、森林的遍历：探度优先第历（先月底怎

14、和需鹫蹩？皿1广度忧去遁历（层执】 先根遍历：访问根结点；依次先根遍历根结点的每棵子树。 后根遍历：依次后根遍历根结点的每棵子树；访问根结点。讨论： 树若采用“先转换，后遍历”方式，结果是否一样？1 .树的先根遍历与二叉树的先序遍历相同；2 .树的后根遍历相当于二叉树的中序遍历；3 .树没有中序遍历，因为子树无左右之分。淼林的逼历先序遍历深度优先遍历先序、申序）广度优先遍历层次1若森林为空，返回；访问森林中第一棵树的根结点； 先根遍历第一棵树的根结点的子树森林； 先根遍历除去第一棵树之后剩余的树构成的森林。中序遍历若森林为空，返回；中根遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点

15、； 中根遍历除去第一棵树之后剩余的树构成的森林。二叉树的应用：哈夫曼树和哈夫曼编码。Huffman树：最优二叉树（带权路径长度最短的树） Huffman编码：不等长编码。树的带权路径长度：（树中所有叶子结点的带权路径长度之和）构造Huffman树的基本思想：权值大的结点用短 路径，权值小的结点用长路径。构造Huffman树的步骤（即Huffman算法）：（1）由给定的n个权值 w1, w2, , , wn 构成n棵二叉树的集合F = T1,T2, , ,Tn）（即森林），其中每棵 二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。（2）在F中选取两棵根结点权值最小的树做为左右子树构造一棵

16、新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。（3）在F中删去这两棵树，同时将新得到的二叉树加入F中。重复和，直到F只含一棵树为止。这棵树便是Huffman树。具体操作步骤：stepl：对权值进行合并、删除与替换在权值束合忡,52 4中，总是合井当的最小的两个权。.初始令并国同吐合井(7) (11FH7K11Ft 11田回团b.合并2 4Ft(7)(5)(6step2：按左“（T右F对Htlffman树的所有分支编号将Huffman树与Huffman八码挂钩a 21 ri nHuffinan 编码结果：d=: , i= t a- JO, n=WFL=lbitX7+2MtX

17、5+3bitQ+4 ） =35 （小干尊长码的 ffFL=36）学习重点：（本章内容是本课程的重点）二叉树性质及证明方法，并能把这种方法推广到K叉树。二叉树遍历，遍历是基础，由此导出许多实用的算法，如求二叉树的高度、各结点的层次数、度为0、1、2的结 点数。由二叉树遍历的前序和中序序列或后序和中序序列可以唯一构造一棵二叉树。由前序和后序序列不能唯一确定一棵 二叉树。完全二叉树的性质。树、森林和二叉树间的相互转换。哈夫曼树的定义、构造及求哈夫曼编码。补充：1-满二叉树和完全二叉树有什么区别？k-1层是满的，但最底层却允许答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前在右边缺少连续若干个结点

18、。满二叉树是完全二叉树的一个特例。2. Huffman树有什么用？最小冗余编码、信息高效传输第七章图内容提要：图的定义，概念、术语及基本操作。图：记为G=（V, E ）其中：V是G的顶点集合，是有穷非空集；E是G的边集合，是有穷集。术语：见课件图的存储结构。1 邻接矩阵（数组）表示法建立一个顶点表和一个邻接矩阵 设图A = （V, E）有n个顶点，则图的邻接矩阵是一个二维数组A.Edgenn。注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧（即出度边）；第i列含义：以结点vi为头的弧（即入度边）。邻接矩阵法优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧） 找顶点的邻

19、接点等等。邻接矩阵法缺点：n个顶点需要n*n个单元存储边（弧）；空间效率为0 （n2）。2邻接表（链式）表示法对每个顶点vi建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为3 个域：头站点表蛤点 每个单链表还应当附设一个头结点（设为2个域），存vi信息；每个单链表的头结点另外用顺序存储结构存储。邻接表的优点：空间效率高；容易寻找顶点的邻接点；邻接表的缺点：判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。图的遍历。遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本

20、运算。图常用的遍历：一、深度优先搜索；二、广度优先搜索 深度优先搜索（遍历）步骤：访问起始点v; 若v的第1个邻接点没访问过，深度遍历此邻接点； 若当前邻接点已访问过，再找v的第2个邻接点重新遍历。基本思想：一一仿树的先序遍历过程。L应退回到Y8,因为V2已有标记广度优先搜索（遍历）步骤：vlTv2Tv4Tv8 Tv5v3Tv6T 在访问了起始点V之后，依次访问V的邻接点； 然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点;直到所有顶点都被访问过为止。图的应用（最小生成树，最短路经）最小生成树（MST ）的性质如下：若U集是V的一个非空子集，若（uO, vO）是一条最小权值的边，其中

21、 uO U , vO V-U ；则：（uO, vO）必在最小生成树上。求MST最常用的是以下两种：Kruskal （克鲁斯卡尔）算法、Prim （普里姆）算法Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。Prime算法特点：将顶点归并,与边数无关，适于稠密网。Kruskal法示刚：对边操作*旧井边在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。 两种常见的最短路径问题：一、单源最短路径一用Dijkstra （迪杰斯特拉）算法二、所有顶点间的最短路径一用Floyd （弗洛伊德）算法一、单源最短路径（Dijkstra算法）一顶点到其

22、余各顶点（vOj）目的：设一有向图G= （V, E）,已知各边的权值，以某指定点V。为源点，求从vO到图的其余各点的最短路径。限定各边上的权值大于或等于0。二、所有顶点之间的最短路径可以通过调用n次Dijkstra算法来完成，还有更简单的一个算法：Floyd算法（自学）。学习重点：图是应用最广泛的一种数据结构，本章也是这门课程的重点。基本概念中，连通分量，生成树，邻接点是重点。 连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与v2是连通的。如果图中任意一对 顶点都是连通的，则称此图是连通图。非连通图的极大连通子图叫做连通分量。 生成树：是一个极小连通子图，它含有图中全部n个顶点

23、，但只有n-1条边。 邻接点：若（u,v）是E（G）中的一条边，则称u与v互为邻接顶点。图是复杂的数据结构，也有顺序和链式两种存储结构：数组表示法（重点是邻接距阵）和邻接表。这两种存储结构 对有向图和无向图均适用应熟练掌图的遍历是图的各种算法的基础，应熟练掌握图的深度、广度优先遍历。连通图的最小生成树不是唯一的，但最小生成树边上的权值之和是唯一的。握prim和kruscal算法，第二章线性表内容提要：线性表的逻辑结构定义，对线性表定义的操作。线性表的定义：用数据元素的有限序列表示n为元素兑口时称为空眈 曾：器线性表的存储结构：顺序存储结构和链式存储结构。顺序存储定义：把逻辑上相邻的数据元素存储

24、在物理上相邻的存储单元中的存储结构。链式存储结构：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上定相邻。通过指针来实现！不一线性表的操作在两种存储结构中的实现。数据结构的基本运算：修改、插入、删除、查找、排序1)修改一一通过数组的下标便可访问某个特定元素并修改之。核心语句：Vi=x;顺序表修改操作的时间效率是0(1)2)插入一一在线性表的第i个位置前插入一个元素实现步骤： 将第n至第i位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。注意：事先应判断：插入位置i是否合法？表是否已满？应当符合条件： K i =i;j-)aU+1=aj；ai =x;n+;插入时的平

25、均移动次数为：n(n+1)/2 *( n+1)=n/20(n)3)删除一一删除线性表的第i个位置上的元素实现步骤： 将第i+1至第n位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i是否合法？应当符合条件：Ki n或1,n核心语句：for(j=i+1;jdata： 查找成功，return Kdata : q=p ; p=p-L_child 继续向左搜索K p-data : q=p ; p=p-R_child / 继续向右搜索查找不成功则插入到二叉排序树中s =(BiTree)malloc(sizeof(BiTNode);s-data=K; s -L_child=NULL; s

26、-R_child=NULL;查找不成功，生成一个新结点s,插入到二叉排序树叶子处case t=NULL ： t=s; 若t为空，则插入的结点s作为根结点K data： q-L_child=s; 若 K 比叶子小，挂左边K q-data： q-R_child=s; 若 K 比叶子大，挂右边return OK)二叉排序树的删除操作如何实现？如何删除一个结点？假设：*P表示被删结点的指针；PL和PR分别表示*P的左、右孩子指针；若在A的Lp子甘的挖亍时上J*人姑A,血乂的*断因子从塔扣至签5E事却疔顾Mfi驴齐建时针如 / 、J 鼻 人的佶Ju0/撬转匚二学习重点：查找表是称为集合的数据结构。因元素

27、间关系非常松散，其操作需借助其它数据结构来实现。本章列举了三种方法 (静态查找表，动态查找表)实现查找表的运算。顺序表因设置了监视哨使查找效率大大提高。有序表的平均查找长度不超过树的深度。*f表示*P的双亲结点指针；并假定*P是*f的左孩子；则可能有三种情况:I巾为叶了 L JW除此结点时“直接悔改曲域即可： 彳打只有Tt 了讨（虹或右）土锂卑吃为*f曲左曲子即町：I衍有两操子楂上悟况矍琳4查找的ASL二叉排序树的形态取决于元素的输入顺序。按中序遍历可得到结点的有序序列，应熟练掌握其建立、查找，插入和 删除算法。平衡二叉树的概念，应熟练掌握手工绘制平衡二叉树。二叉排序树的AS. LL平衡旋转：

28、3) LR平衡康转:若灰A的士子甘的右子+人上J6人人A, TitA的辛街因子从L堆加生7,需奂st琨好够叶汁程转.再4) RL平衡族转:ASLoK的记录,补充：1 .查找的过程是怎样的？给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于如找到则输出该记录，否则输出查找不成功的信息。2 .对查找表常用的操作有哪些？查询某个“特定的”数据元素是否在表中；查询某个“特定的”数据元素的各种属性；在查找表中插入一元素； 从查找表中删除一元素。3 .哪些查找方法？查找方法取决于表中数据的排列方式；4 .如何评估查找方法的优劣？用比较次数的平均值来评估算法的优劣。称为平均查找长度ASL=r

29、 Pi. Ci 5,使用折半查找算法时，要求被查文件：采用顺序存贮结构、记录按关键字递增有序6.将线性表构造成二叉排序树的优点： 查找过程与顺序结构有序表中的折半查找相似，查找效率高； 中序遍历此二叉树，将会得到一个关键字的有序序列(即实现了排序运算)； 如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需 移动元素。第九章内部排序内容提要：排序的定义，排序可以看作是线性表的一种操作排序:将一组杂乱无章的数据按一定的规律顺次排列起来。排序的分类，稳定排序与不稳定排序的定义。稳定性一一若两个记录A和B的关键字值相等，但排序后则称这种排序算A、B的先后次

30、序保持不变，法是 稳定的。插入排序(直接插入、折半插入，索引表插入、希尔插入排序)插入排序的基本思想是：描入排序有多种具体宴现算法:I)亘樱插入排序力折半插入排序3) 2-路插入排序-小改进4)祓描入排序J5)希尔排序一大克讲0+ 1+ , + 尸 O(n2)。每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对 象的适当位置上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。1)直接插入排序在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素 向后顺移。例1;关镇字住列T- (13, 6阑31,篦27, 5, 11), 请写出直接插入排序

31、的4同过程序列*13，电气 31,9,27/41【6,13，M 31, % 27,0113,6,13 ,31,9,37113,6,13*3127,5,113,31 5,11【3(* 13, 27,311,5,11【3,久19箕 27t JI ,11 3A IK 13, 27,31时间效率：因为在最坏情况下，所有元素的比较次数总和为(其他情况下也要考虑移动元素的次数。故时间复杂度为0( n2)空间效率：仅占用 1个缓冲单元一一 O(1)算法的稳定性：因为25*排序后仍然在25的后面一一稳定直接插入排序算法的实现：void InsertSort ( SqList &L ) /对顺序表L作直接插入排

32、序for(i = 2;i=L.length;i+)/ 假定第一个记录有序 L.rO= L.ri;j=i-1 ；先将待插入的元素放入“哨兵”位置while(L0 .keyT）由经验公式得到空间效率0（1； 一一因为仅占用1个缓冲单云算法的膛定性：不稳定一一为4中排序后却封了翻的前血交换排序（冒泡排序、快速排序）。交换排序的基本思想是：两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相 反），则交换之，直到所有记录都排好序为止。1）冒泡排序基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时

33、部分理顺其他元素；旦下趟没有交换发生，还可以提前结 束排序。 前提：顺序存储结构例：关键字序列T=（21 25, 49. 25*t 08） * ifl写出目泡排序的具悴实现过程。2L 25,49T 25*, 14. 0821.25,15* 16, 08t49 Z, 25, 16h OR *4921,16, U8f 25, 2S*t 4916, 08 21, 25, 25S 4908,16. 21,25. 25 49冒泡排序的算法分析：时间效率：。（n2）因为要考虑最坏情况空间效率：。（1）一只在交换时用到一个缓冲单元稳定性：稳定一 25和25*在排序前后的次序未改变冒泡排序的优点：每一趟整理元

34、素时，不仅可以完全确定一个元素的位置尾），还可以对前面（挤出一个泡到表 的元素作一些整理，所以比一般的排序要快。2）快速排序基本思想：从待排序列中任取一个元素（例如取第一个）作为中心，所有比它小的元素一律前放，所有比它大的元 素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩 一个。此时便为有序序列了。优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！前提：顺序存储结构例仁 关键字序7 八（21, 25, 49, 25*, 16, 08）.请写出快速排序的设以首元素为枢轴中社.初态：21, 25, 49, 25*, 1氐08第 1 趟：（08 1621 口（25*, 49,25）第 2 趟* （08）r 16A 21, 25*, 25, 49）第第嵌 08r 16,27, 25S 25. （49）时间效率：0（nl og2 n）因为每趟确定的元素呈指数增加空间效率：0（Iog2n）因为递归要用栈（存每层low , high和pivot）稳定性：不稳定一因为有跳跃式交换。选择排序（简单选择排序、树形选择排序、堆排序）。选择排序的基本思想是：每一趟在后面n-i