数据结构知识点总结[3].docx

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

1、数据构造学问点概括第一章 概 论数据就是指能够被计算机识别, 存储和加工处理的信息的载体。数据元素是数据的根本单位，可以由假设干个数据项组成。数据项是具有独立含义的最小标识单位。数据构造的定义：逻辑构造：从逻辑构造上描述数据，独立于计算机。线性构造：一对一关系。线性构造：多对多关系。存储构造：是逻辑构造用计算机语言的实现。依次存储构造：如数组。链式存储构造：如链表。索引存储构造：稠密索引：每个结点都有索引项。稀疏索引：每组结点都有索引项。散列存储构造：如散列表。数据运算。对数据的操作。定义在逻辑构造上，每种逻辑构造都有一个运算集合。常用的有：检索, 插入, 删除, 更新, 排序。数据类型：是一

2、个值的集合以及在这些值上定义的一组操作的总称。构造类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型：是抽象数据的组织和及之的操作。相当于在概念层上描述问题。 优点是将数据和操作封装在一起实现了信息隐藏。程序设计的实质是对实际问题选择一种好的数据构造，设计一个好的算法。算法取决于数据构造。算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。评价算法的好坏的因素：算法是正确的；执行算法的时间；执行算法的存储空间主要是协助存储空间；算法易于理解, 编码, 调试。时间困难度：是某个算法的时间消耗，它是该算法所求解问题规模的函数。渐近时间困难度：是指当问题规模趋向无穷大时，该

3、算法时间困难度的数量级。评价一个算法的时间性能时，主要标准就是算法的渐近时间困难度。算法中语句的频度不仅及问题规模有关，还及输入实例中各元素的取值相关。时间困难度按数量级递增排列依次为：常数阶, 对数阶, 线性阶, 线性对数阶, 平方阶, 立方阶, 次方阶, 指数阶。空间困难度：是某个算法的空间消耗，它是该算法所求解问题规模的函数。算法的时间困难度和空间困难度合称算法困难度。第二章 线性表线性表是由个数据元素组成的有限序列。是空表；非空表，只能有一个开场结点，有且只能有一个终端结点。线性表上定义的根本运算：构造空表：求表长：取结点：，查找：，插入：，删除：，依次表是按线性表的逻辑构造次序依次存

4、放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑构造中各结点相邻关系是一样的。地址计算：*；首地址为在依次表中实现的根本运算：插入：平均移动结点次数为；平均时间困难度均为。 删除：平均移动结点次数为；平均时间困难度均为。线性表的链式存储构造中结点的逻辑次序和物理次序不肯定一样，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息即指针或链。这两局部信息组成链表中的结点构造。 一个单链表由头指针的名字来命名。单链表运算：建立单链表头插法：；生成的依次及输入依次相反。平均时间困难度均为。尾插法：； ； ； 平均时间困难度均为加头结点的算法：对开场结

5、点的操作无需特别处理，统一了空表和非空表。查找按序号：及查找位置有关，平均时间困难度均为。按值：及输入实例有关，平均时间困难度均为。插入运算：，；平均时间困难度均为删除运算：，；平均时间困难度均为单循环链表是一种首尾相接的单链表，终端结点的指针域指向开场结点或头结点。链表终止条件是以指针等于头指针或尾指针。采纳单循环链表在好用中多采纳尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是，不用遍历整个链表。双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其干脆前趋的指针域，形成两条不同方向的链。由头指针惟一确定。双链表也可以头尾相链接构成双向循环链表。双链表上的插入和删除时间困难度

6、均为 。依次表和链表的比拟：基于空间： 依次表的存储空间是静态安排，存储密度为；适于线性表事先确定其大小时采纳。链表的存储空间是动态安排，存储密度；适于线性表长度变更大时采纳。基于时间：依次表是随机存储构造，当线性表的操作主要是查找时，宜采纳。以插入和删除操作为主的线性表宜采纳链表做存储构造。假设插入和删除主要发生在表的首尾两端，那么宜采纳尾指针表示的单循环链表。第三章 栈和队列栈是仅限制在表的一端进展插入和删除运算的线性表，称插入, 删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原那么进展的，我们又称栈为表 。通常栈有依次栈和链栈两种存储构造。栈的根本运算有六种

7、： 构造空栈：判栈空： 判栈满： 进栈： ，退栈： 取栈顶元素：在依次栈中有“上溢和“下溢的现象。 “上溢是栈顶指针指出栈的外面是出错状态。“下溢可以表示栈为空栈，因此用来作为限制转移的条件。依次栈中的根本操作有六种：构造空栈 判栈空 判栈满 进栈 退栈 取栈顶元素链栈那么没有上溢的限制，因此进栈不要判栈满。链栈不须要在头部附加头结点，只要有链表的头指针就可以了。链栈中的根本操作有五种：构造空栈 判栈空 进栈 退栈 取栈顶元素队列是一种运算受限的线性表，插入在表的一端进展，而删除在表的另一端进展，允许删除的一端称 为队头，允许插入的一端称为队尾 ，队列的操作原那么是先进先出的，又称作表 .队列

8、也有依次存储和链式存储两种存储构造。队列的根本运算有六种：置空队：判队空：判队满：入队：，出队：取队头元素：依次队列的“假上溢现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了“上溢现象。为了克制“假上溢现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。判定循环队列是空还是满，方法有三种： 一种是另设一个布尔变量来推断；第二种是少用一个元素空间，入队时先测试 ？ 满：空；第三种就是用一个计数器记录队列中的元素的总数。队列的链式存储构造称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进展插入入队的 操作，在表尾增加一个尾指针

9、，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中，要留意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。第四章 串串是零个或多个字符组成的有限序列。空串：是指长度为零的串，也就是串中不包含任何字符结点。空白串：指串中包含一个或多个空格字符的串。在一个串中随意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。子串在主串中的序号就是指子串在主串中首次出现的位置。空串是随意串的子串，随意串是自身的子串。串分为两种： 串常量在程序中只能引用不能变更；串变量的值可以变更。串的根本运算有： 求串长*串复制*，*串联接*，*串比拟

10、*，*字符定位*，串是特别的线性表结点是字符，所以串的存储构造及线性表的存储构造类似。串的依次存储构造简称为依次串。依次串又可按存储安排的不同分为： 静态存储安排：干脆用定长的字符数组来定义。优点是涉及串长的操作速度 快，但不适合插入, 链接操作。动态存储安排：是在定义串时不安排存储空间，须要运用时按所需串的长度安排存储单元。串的链式存储就是用单链表的方式存储串值，串的这种链式存储构造简称为链串。链串及单链表的差异只是它的 结点数据域为单个字符。为了解决“存储密度低的状况，可以让一个结点存储多个字符，即结点的大小。依次串上子串定位的运算：又称串的“模式匹配或“串匹配，是在主串中查找出子串出现的

11、位置。在串匹配中，将主串称为目标串，子串称为模式串。这是比拟简洁理解的，串匹配问题就是找出给定模式串在给定目标串中首次出现的有效位移或者是全部有效位移。最坏的状况下时间困难度是，假设及同阶的话那么它是。链串上的子串定位运算位移是结点地址而不是整数第五章 多维数组数组一般用依次存储的方式表示。存储的方式有： 行优先依次，也就是把数组逐行依次排列。, 列优先依次，就是把数组逐列依次排列。地址的计算方法： 按行优先依次排列的数组：*. 按列优先依次排列的数组：*.矩阵的压缩存储：为多个一样的非零元素安排一个存储空间；对零元素不安排空间。特别矩阵的概念：所谓特别矩阵是指非零元素或零元素分布有肯定规律的

12、矩阵。稀疏矩阵的概念：一个矩阵中假设其非零元素的个数远远小于零元素的个数，那么该矩阵称为稀疏矩阵。 特别矩阵的类型： 对称矩阵：满意。元素总数，*.三角矩阵： 上三角阵：*，*. 下三角阵：*，*.对角矩阵：，*.稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表来表示。但这种压缩存储方式将失去随机存储功能。参与行表记录每行的非零元素在三元组表中的起始位置，即带行表的三元组表。第六章 树树是个结点的有限集合，非空时必需满意：只有一个称为根的结点；其余结点形成个不相交的子集，并称根的子树。根是开场结点；结点的子树数称度；度为的结点称

13、叶子终端结点；度不为的结点称分支结点非终端结点；除根外的分支结点称内部结点；有序树是子树有左，右之分的树；无序树是子树没有左，右之分的树；森林是个互不相交的树的集合；树的四种不同表示方法：树形表示法；嵌套集合表示法；凹入表示法广义表表示法。二叉树的定义：是个结点的有限集，它是空集或由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。二叉树不是树的特别情形，及度数为的有序树不同。二叉树的个重要性质： 二叉树上第层上的结点数目最多为。；深度为的二叉树至多有个结点；在随意一棵二叉树中，假设终端结点的个数为，度为的结点数为，那么；具有个结点的完全二叉树的深度为.满二叉树是一棵深度为

14、，结点数为的二叉树；完全二叉树是满二叉树在最下层自右向左去处局部结点；二叉树的依次存储构造就是把二叉树的全部结点依据层次依次存储到连续的存储单元中。存储前先将其画成完全二叉树树的存储构造多用的是链式存储。的构造为，把全部类型的结点，加上一个指向根结点的型头指针就构成了二叉树的链式存储构造，称为二叉链表。它就是由根指针唯一确定的。共有个指针域，个空指针。依据访问结点的次序不同可得三种遍历：先序遍历前序遍历或先根遍历，中序遍历或中根遍历, 后序遍历或后根遍历。时间困难度为。利用二叉链表中的个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就称为“线索，加上线索的二叉链表就

15、称为线索链表。线索使得查找中序前趋和中序后继变得简洁有效，但对于查找指定结点的前序前趋和后序后继并没有什么作用。树和森林及二叉树的转换是唯一对应的。转换方法： 树变二叉树：兄弟相连，保存长子的连线。二叉树变树：结点的右孩子及其双亲连。森林变二叉树：树变二叉树，各个树的根相连。树的存储构造：有双亲链表表示法：结点 ，对于求指定结点的双亲或祖先非常便利，但不适于求指定结点的孩子及后代。孩子链表表示法：为树中每个结点 设置一个孩子链表，并将 存放在一个向量中。双亲孩子链表表示法：将双亲链表和孩子链表结合。孩子兄弟链表表示法：结点构造 ，附加两个分别指向该结点的最左孩子和右邻兄弟的指针域。树的前序遍历

16、及相对应的二叉树的前序遍历一样；树的后序遍历及相对应的二叉树的中序遍历一样。树的带权路径长度是树中全部叶结点的带权路径长度之和。树的带权路径长度最小的二叉树就称为最优二叉树即哈夫曼树。在叶子的权值一样的二叉树中，完全二叉树的路径长度最短。哈夫曼树有个叶结点，共有个结点，没有度为的结点，这类树又称为严格二叉树。变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码可能使解码产生二义性。如, , 这三个码无法在解码时确定是哪一个，所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀，这种码称为前缀码其实是非前缀码。哈夫曼树的应用最广泛地是在编码技术上，它能够简洁地求出给定字

17、符集及其概率分布的最优前缀码。哈夫曼编码的构造很简洁，只要画好了哈夫曼树，按分支状况在左路径上写代码，右路径上写代码，然后从上到下到叶结点的相应路径上的代码的序列就是该结点的最优前缀码。第七章 图图的逻辑构造特征就是其结点顶点的前趋和后继的个数都是没有限制的，即随意两个结点之间之间都可能相关。图，是顶点的有穷非空集合，是顶点偶对的有穷集。有向图：每条边有方向；无向图：每条边没有方向。有向完全图：具有*条边的有向图；无向完全图：具有*条边的无向图；有根图：有一个顶点有路径到达其它顶点的有向图；简洁路径：是经过顶点不同的路径；简洁回路是开场和终端重的简洁路径；网络：是带权的图。图的存储构造：邻接矩

18、阵表示法：用一个阶方阵来表示图的构造是唯一的，适合稠密图。无向图：邻接矩阵是对称的。有向图：行是出度，列是入度。建立邻接矩阵算法的时间是，其时间困难度为邻接表表示法：用顶点表和邻接表构成不是唯一的，适合稀疏图。顶点表构造 ，指针域存放邻接表头指针。邻接表：用头指针确定。 无向图称边表；有向图又分出边表和逆邻接表；邻接表结点构造为 ，时间困难度为。，空间困难度为。图的遍历： 深度优先遍历：借助于邻接矩阵的列。运用栈保存已访问结点。广度优先遍历：借助于邻接矩阵的行。运用队列保存已访问结点。生成树的定义：假设从图的某个顶点动身，可以系统地访问到图中全部顶点，那么遍历时经过的边和图的全部顶点构成的子图

19、称作该图的生成树。最小生成树：图的生成树不唯一，从不同的顶点动身可得到不同的生成树，把权值最小的生成树称为最小生成树。构造最小生成树的算法： 算法的时间困难度为及边数无关适于稠密图。算法的时间困难度为，主要取决于边数，较适合于稀疏图。最短路径的算法：算法，时间困难度为。类似于算法。拓扑排序：是将有向无环图中全部顶点排成一个线性序列，假设，那么在线性序列在之前，这种线性序列称为拓扑序列。拓扑排序也有两种方法：无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最终得到的序列即拓扑序列。无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边，最终得到的序列是逆拓扑序列。第八章

20、排序记录中可用某一项来标识一个记录，那么称为关键字项，该数据项的值称为关键字。排序是使文件中的记录按关键字递增或递减次序排列起来。根本操作：比拟关键字大小；变更指向记录的指针或移动记录。存储构造：依次构造, 链表构造, 索引构造。经过排序后这些具有一样关键字的记录之间的相对次序保持不变，那么称这种排序方法是稳定的，否那么排序算法是不稳定的。排序过程中不涉及数据的内, 外存交换那么称之为“内部排序内排序，反之，假设存在数据的内外存交换，那么称之为外排序。内部排序方法可分五类：插入排序, 选择排序, 交换排序, 归并排序和安排排序。评价排序算法好坏的标准主要有两条：执行时间和所需的协助空间，另外算

21、法的困难程序也是要考虑的一个因素。插入排序：干脆插入排序： 逐个向前插入到相宜位置。哨兵监视哨有两个作用： 作为临变量存放是在查找循环中用来监视下标变量是否越界。干脆插入排序是就地的稳定排序。时间困难度为，比拟次数为；移动次数为；希尔排序： 等间隔的数据比拟并按要求依次排列，最终间隔为.希尔排序是就地的不稳定排序。时间困难度为，比拟次数为；移动次数为；交换排序：冒泡排序：自下向上确定最轻的一个。自上向下确定最重的一个。自下向上确定最轻的一个，后自上向下确定最重的一个。冒泡排序是就地的稳定排序。时间困难度为，比拟次数为；移动次数为；快速排序：以第一个元素为参考基准，设定, 动两个指针，发生交换后

22、指针交换位置，直到指针重合。重复直到排序完成。快速排序是非就地的不稳定排序。时间困难度为，比拟次数为；选择排序：干脆选择排序： 选择最小的放在比拟区前。干脆选择排序就地的不稳定排序。时间困难度为。比拟次数为；堆排序 建堆：按层次将数据填入完全二叉树，从处向前逐个调整位置。然后将树根及最终一个叶子交换值并断开及树的连接并重建堆，直到全断开。堆排序是就地不稳定的排序，时间困难度为，不相宜于记录数较少的文件。归并排序： 先两个一组排序，形成组，再将两组并一组，直到剩下一组为止。归并排序是非就地稳定排序，时间困难度是，安排排序：箱排序： 按关键字的取值范围确定箱子数，按关键字投入箱子，链接全部非空箱。

23、箱排序的平均时间困难度是线性的。基数排序：从低位到高位依次对关键字进展箱排序。基数排序是非就稳定的排序，时间困难度是*。各种排序方法的比拟和选择： 待排序的记录数目；较大的要用时间困难度为的排序方法；记录的大小规模；记录大最好用链表作为存储构造，而快速排序和堆排序在链表上难于实现；关键字的构造及其初始状态；对稳定性的要求；语言工具的条件； 存储构造；时间和协助空间困难度。第九章 查找查找的同时对表做修改操作如插入或删除那么相应的表称之为动态查找表，否那么称之为静态查找表。衡量查找算法效率优劣的标准是在查找过程中对关键字须要执行的平均比拟次数即平均查找长度。线性表查找的方法： 依次查找：逐个查找

24、，；二分查找：取中点比拟，假设小就比左区间，大就比右区间。用二叉判定树表示。每层结点数*层数.分块查找。要求“分块有序，将表分成假设干块内部不肯定有序，并抽取各块中的最大关键字及其位置建立有序索引表。二叉排序树定义是：二叉排序树是空树或者满意如下性质的二叉树： 假设它的左子树非空，那么左子树上全部结点的值均小于根结点的值；假设它的右子树非空，那么右子树上全部结点的值均大于根结点的值；左, 右子树本身又是一棵二叉排序树。二叉排序树的插入, 建立, 删除的算法平均时间性能是。二叉排序树的删除操作可分三种状况进展处理： *是叶子，那么干脆删除*，即将*的双亲*中指向*的指针域置空即可。*只有一个孩子

25、*，此时只需将*和*的双亲干脆连接就可删去*.*有两个孩子，那么先将*结点的中序后继结点的数据到*，删除中序后继结点。关于树多路平衡查找树。它适合在磁盘等干脆存取设备上组织动态的查找表，是一种外查找算法。建立的方式是从下向上拱起。散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。散列函数的选择有两条标准：简洁和匀称。常见的散列函数构的造方法：平方取中法：除余法：表长为，相乘取整法：*； 随机数法：。处理冲突的方法：开放定址法： 一般形式为，开放定址法要求散列表的装填因子. 开放定址法类型： 线性探查法：；二次探查法：； 双重散列法：*； 拉链法： 是将全部关键字为同义词的结点链接

26、在同一个单链表中。 拉链法的优点： 拉链法处理冲突简洁，且无积累现象； 链表上的结点空间是动态申请的适于无法确定表长的状况； 拉链法中可以大于，结点较大时其指针域可忽视，因此节约空间；拉链法构造的散列表删除结点易实现。拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。第十章 排序 排序的根本概念 插入排序 选择排序 交换排序本章主要学问点：排序的根本概念和衡量排序算法优劣的标准，其中衡量标准有算法的时间困难度, 空间困难度和稳定性干脆插入排序，希尔排序干脆选择排序，堆排序冒泡排序，快速排序排序的根本概念.排序是对数据元素序列建立某种有序排列的过程。.排

27、序的目的：便于查找。.关键字是要排序的数据元素集合中的一个域，排序是以关键字为基准进展的。 关键字分主关键字和次关键字两种。对要排序的数据元素集合来说，假如关键字满意数据元素值不同时该关键字的值也肯定不同，这样的关键字称为主关键字。不满意主关键字定义的关键字称为次关键字。.排序的种类：分为内部排序和外部排序两大类。 假设待排序记录都在内存中，称为内部排序；假设待排序记录一局部在内存，一局部在外存，那么称为外部排序。 注：外部排序时，要将数据分批调入内存来排序，中间结果还要刚好放入外存，明显外部排序要困难得多。 .排序算法好坏的衡量标准：()时间困难度 它主要是分析记录关键字的比拟次数和记录的移

28、动次数。()空间困难度算法中运用的内存协助空间的多少。()稳定性假设两个记录和的关键字值相等，但排序后, 的先后次序保持不变，那么称这种排序算法是稳定的。 插入排序 插入排序的根本思想是：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。 简言之，边插入边排序，保证子序列中随时都是排好序的。 常用的插入排序有：干脆插入排序和希尔排序两种。10 干脆插入排序, 其根本思想是： 依次地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。 例：关键字序列，请写出干脆插入排序的中间过程序列。初始关键字序列：【】, , , ,

29、 , , , 第一次排序： 【, 】, , , , , , 第二次排序： 【, , 】, , , , , 第三次排序： 【, , ，】, , , , 第四次排序： 【, , , ，】, , , 第五次排序： 【, , , ，, 】, , 第六次排序： 【, , , , ，, 】, 第七次排序： 【, , , , ，, 】 注：方括号 中为已排序记录的关键字，下划横线的 关键字表示它对应的记录后移一个位置。.干脆插入排序算法 ( ) , , ; ;( ; ) ; ; ;初始关键字序列：【】, , , , , , , 第一次排序： 【, 】, , , , , , 第二次排序： 【, , 】, ,

30、, , , , 干脆插入排序算法分析()时间效率：当数据有序时，执行效率最好，此时的时间困难度为()；当数据根本反序时，执行效率最差，此时的时间困难度为()。所以当数据越接近有序，干脆插入排序算法的性能越好。 ()空间效率：仅占用个缓冲单元 ()算法的稳定性：稳定 希尔排序 又称缩小增量排序, 根本思想：把整个待排序的数据元素分成假设干个小组，对同一小组内的数据元素用干脆插入法排序；小组的个数逐次缩小，当完成了全部数据元素都在一个组内的排序后排序过程完毕。 , 技巧：小组的构成不是简洁地“逐段分割，而是将相隔某个增量的记录组成一个小组,让增量逐趟缩短例如依次取，直到为止。, 优点：让关键字值小

31、的元素能很快前移，且序列假设根本有序时，再用干脆插入排序处理，时间效率会高许多。例：设待排序的序列中有个记录，它们的关键字序列 (，请写出希尔排序的详细实现过程。 ( , , ) , , , , ; ; ;( ; ; )共次循环 ; 取本次的增量值( ; ; )共个小组( ; ) ; ; ;算法分析：开场时 的值较大，子序列中的对象较少，排序速度较快；随着排序进展， 值渐渐变小，子序列中对象个数渐渐变多，由于前面工作的根底，大多数记录已根本有序，所以排序速度仍旧很快。 时间效率：() 空间效率：因为仅占用个缓冲单元 算法的稳定性：不稳定 练习：. 欲将序列, , , , , , , , , ,

32、 , 中的关键码按字母升序重排，那么初始为的希尔排序一趟的结果是？答： 原始序列： , , , , , , , , , , , 一趟后： . 以关键字序列，为例，写出执行希尔排序取算法的各趟排序完毕时，关键字序列的状态。解：原始序列: ，希尔排序第一趟 第二趟 第三趟 选择排序 选择排序的根本思想是：每次从待排序的数据元素集合中选取关键字最小或最大的数据元素放到数据元素集合的最前或最终，数据元素集合不断缩小，当数据元素集合为空时选择排序完毕。常用的选择排序算法： 干脆选择排序 堆排序10干脆选择排序, 其根本思想 每经过一趟比拟就找出一个最小值，及待排序列最前面的位置互换即可。即从待排序的数据

33、元素集合中选取关键字最小的数据元素并将它及原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置的数据元素集合中选取关键字最小的数据元素并将它及原始数据集合中的第二个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数据元素为止。, 优缺点优点：实现简洁缺点：每趟只能确定一个元素，表长为时须要趟例：关键字序列 ，*，请给出干脆选择排序的详细实现过程。原始序列： ，*，第趟 ，*，第趟 ，, ，*，第趟 ，, ，*，第趟 ，, ，*，第趟 ，, ，*， ( ) , , ; ; ;( ; ; ) ; 设第个数据元素最小 ( ; ; )找寻最小的数据元素 ( ) ; 记住最小元素的下

34、标 ( ) 当最小元素的下标不为时交换位置 ; ; ; , 算法分析时间效率： ()虽移动次数较少，但比拟次数仍多。 空间效率：没有附加单元仅用到个)算法的稳定性：不稳定, 稳定的干脆选择排序算法例：关键字序列 ，*，请给出稳定的干脆选择排序的详细实现过程。原始序列： ，*，第趟, , , , *, 第趟，, ， ， *第趟，, ， ， *第趟，, ， ， *第趟，, ， * ， ( ) ; ; ;( ; ; ) ; ( ; ; ) 找寻最小的数据元素 ( ; ) 把该区段尚未排序元素依次后移 ; ; 插入找出的最小元素 堆排序. 什么是堆？ . 怎样建堆？ . 怎样堆排序？堆的定义：设有个数

35、据元素的序列 ，当且仅当满意下述关系之一时，称之为堆。 说明：假如让满意以上条件的元素序列 ，顺次排成一棵完全二叉树，那么此树的特点是： 树中全部结点的值均大于或小于其左右孩子，此树的根结点即堆顶必最大或最小。例：有序列, , , , , 和序列, , , , , , ,推断它们是否 “堆？. 怎样建堆？步骤：从第一个非终端结点开场往前逐步调整，让每个双亲大于或小于子女，直到根结点为止。终端结点即叶子没有任何子女，无需单独调整例：关键字序列 (，*，请建最大堆。解：为便于理解，先将原始序列画成完全二叉树的形式： 这样可以很清楚地从()开场调整。 ( , , ) , , ; ; ; * ; 为结

36、点的左孩子结点的下标 ; ; ( )找寻左右孩子结点中的较大者为其下标( ) ; 标记完毕筛选条件否那么把上移 ; ; * ; ; 利用上述函数，初始化创立最大堆的过程就是从第一个非叶子结点开场，到根结点为止，循环调用的过程。初始化创立最大堆算法如下： ( ) ;( () ; ; )(, , );. 怎样进展整个序列的堆排序？*基于初始堆进展堆排序的算法步骤： 堆的第一个对象具有最大的关键码，将及对调，把具有最大关键码的对象交换到最终;再对前面的个对象，运用堆的调整算法，重新建立堆调整根结点使之满意最大堆的定义。结果具有次最大关键码的对象又上浮到堆顶，即位置;再对调和，然后对前个对象重新调整，

37、如此反复，最终得到全部排序好的对象序列。例：对刚刚建好的最大堆进展排序： ( ) ; ;(); 初始化创立最大堆( ; ; )当前最大堆个数每次递减把堆顶元素和当前最大堆的最终一个元素交换 ; ; ;(, ); 调整根结点满意最大堆, 堆排序算法分析：时间效率：()。空间效率：()。稳定性： 不稳定。练习：以下序列是堆的是 . . . 练习：有一组数据*，建成的最小堆为 。.* .*.* .以上都不对练习：序列，写出采纳堆排序对该序列作非递减排列时的排序过程。排序好的序列为：， 交换排序交换排序的根本思想是：利用交换数据元素的位置进展排序的方法。交换排序的主要算法有： ) 冒泡排序 ) 快速排序10 冒泡排序, 根本思路：每趟不断将记录两两比拟，并按“前小后大或“前大后小规那么交换。, 优点：每趟完毕时，不仅能挤出一个最大值到最终面位置，还能同时局部理顺其他元素；一旦下趟没有交换发生，还可以提前完毕排序。例：关键字序列 (，*，请按从小到大的依次，写出冒泡排序的详细实现过程。初态：， *， 第趟，*， ， 第趟， ， ，*，第趟， ， *，第趟， ， ， *，第趟， ， ， *，, 冒泡排序算法 ( ) , , ; ; ;( ; ; ) ;( ; ) ; ; ; ;