2022年非常实用的数据结构知识点总结 2.docx

精品_精品资料_O（nlog2n ）、平方阶 O数据结构学问点概括第一章 概 论数据就是指能够被运算机识别、储备和加工处理的信息的载体.数据元素是数据的基本单位,可以由如干个数据项组成.数据项是具有独立含义的最小标识单位.数据结构的定义：·规律结构：从规律结构上描述数据,独立于运算机. ·线性结构：一对一关系.·线性结构：多对多关系.·储备结构：是规律结构用运算机语言的实现.·次序储备结构：如数组.·链式储备结构：如链表.·索引储备结构：·稠密索引：每个结点都有索引项.·稀疏索引：每组结点都有索引项.·散列储备结构：如散列表.·数据运算.·对数据的操作.定义在规律结构上,每种规律结构都有一个运算集合.·常用的有：检索、插入、删除、更新、排序.数据类型：是一个值的集合以及在这些值上定义的一组操作的总称.·结构类型：由用户借助于描述机制定义,是导出类型.抽象数据类型 ADT：·是抽象数据的组织和与之的操作.相当于在概念层上描述问题.·优点是将数据和操作封装在一起实现了信息隐匿.程序设计的实质是对实际问题挑选一种好的数据结构,设计一个好的算法.算法取决于数据结构.算法是一个良定义的运算过程,以一个或多个值输入,并以一个或多个值输出.评判算法的好坏的因素： ·算法是正确的.·执行算法的时间.·执行算法的储备空间（主要是帮助储备空间）.·算法易于懂得、编码、调试.时间复杂度：是某个算法的时间耗费,它是该算法所求解问题规模n 的函数.渐近时间复杂度：是指当问题规模趋向无穷大时,该算法时间复杂度的数量级.评判一个算法的时间性能时,主要标准就是算法的渐近时间复杂度.算法中语句的频度不仅与问题规模有关,仍与输入实例中各元素的取值相关.时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶 O（ log2n ）、线性阶 O（n ）、线性对数阶（n2 ）、立方阶 O（n3 ）、k 次方阶 O（nk ）、指数阶 O（2n ）.空间复杂度：是某个算法的空间耗费,它是该算法所求解问题规模n 的函数.可编辑资料 - - - 欢迎下载精品_精品资料_算法的时间复杂度和空间复杂度合称算法复杂度.其次章 线性表线性表是由 n 0 个数据元素组成的有限序列.n=0 是空表.非空表,只能有一个开头结点,有且只能有一个终端结点.线性表上定义的基本运算：·构造空表：Initlist （L）·求表长：Listlength（L）·取结点：GetNode （ L, i）·查找：LocateNode（L,x）·插入：InsertList （L,x,i）·删除：Delete （ L, i）次序表是按线性表的规律结构次序依次存放在一组的址连续的储备单元中.在储备单元中的各元素的物理位置和规律结构中各结点相邻关系是一样的.的址运算：LOCa （i） =LOCa （1）+ （ i-1 ） *d .（首的址为 1 ）在次序表中实现的基本运算：·插入：平均移动结点次数为 n/2 .平均时间复杂度均为 O（n ）.·删除：平均移动结点次数为（ n-1 ）/2 .平均时间复杂度均为 O（n ）.线性表的链式储备结构中结点的规律次序和物理次序不肯定相同,为了能正确表示结点间的规律关系,在储备每个结点值的同时, 仍储备了其后继结点的的址信息（即指针或链） .这两部分信息组成链表中的结点结构.一个单链表由头指针的名字来命名.单链表运算：·建立单链表·头插法：s->next=head.head=s .生成的次序与输入次序相反.平均时间复杂度均为O（ n ）.·尾插法：head=rear=null.if （head=null） head=s . else r->next=s.r=s . 平均时间复杂度均为 O（ n）·加头结点的算法：对开头结点的操作无需特别处理,统一了空表和非空表.·查找·按序号：与查找位置有关,平均时间复杂度均为 O（ n）.·按值：与输入实例有关,平均时间复杂度均为 O（n ）.·插入运算：p=GetNode（L, i-1 ）. s->next=p->next. p->next=s.平均时间复杂度均为 O（n）·删除运算：p=GetNode（L,i-1 ）.r=p->next. p->next=r->next. free （r ）.平均时间复杂度均为 O（n）单循环链表是一种首尾相接的单链表,终端结点的指针域指向开头结点或头结点.链表终止条件是以指针等于头指针或尾指针.采纳单循环链表在有用中多采纳尾指针表示单循环链表.优点是查找头指针和尾指针的时间都是O（1 ）,不用遍历整个链表.双链表就是双向链表,就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior ,形成两条不同方可编辑资料 - - - 欢迎下载精品_精品资料_向的链.由头指针 head 惟一确定.双链表也可以头尾相链接构成双（向）循环链表. 双链表上的插入和删除时间复杂度均为O （ 1 ）.次序表和链表的比较：·基于空间：·次序表的储备空间是静态安排,储备密度为 1.适于线性表事先确定其大小时采纳.·链表的储备空间是动态安排,储备密度 1 .适于线性表长度变化大时采纳.·基于时间：·次序表是随机储备结构,当线性表的操作主要是查找时,宜采纳.·以插入和删除操作为主的线性表宜采纳链表做储备结构.·如插入和删除主要发生在表的首尾两端,就宜采纳尾指针表示的单循环链表.第三章 栈和队列栈（ Stack ）是仅限制在表的一端进行插入和删除运算的线性表,称插入、删除这一端为栈顶,另一端称为栈底.表中无元素时为空栈.栈的修改是按后进先出的原就进行的,我们又称栈为LIFO 表（ Last In First Out）.通常栈有次序栈和链栈两种储备结构.栈的基本运算有六种：·构造空栈：InitStack （S）·判栈空：StackEmpty （S）·判栈满：StackFull （S）·进栈：Push （S,x）·退栈：Pop （S）·取栈顶元素：StackTop （S）在次序栈中有“上溢”和“下溢”的现象.·“上溢”是栈顶指针指出栈的外面是出错状态.·“下溢”可以表示栈为空栈,因此用来作为掌握转移的条件.次序栈中的基本操作有六种： ·构造空栈 ·判栈空 ·判栈满 ·进栈 ·退栈 ·取栈顶元素链栈就没有上溢的限制,因此进栈不要判栈满.链栈不需要在头部附加头结点,只要有链表的头指针就可以了.链栈中的基本操作有五种： ·构造空栈 ·判栈空 ·进栈 ·退栈 ·取栈顶元素队列（ Queue ）是一种运算受限的线性表,插入在表的一端进行,而删除在表的另一端进行,答应删除的一端称为队头（ front ）,答应插入的一端称为队尾（ rear ） ,队列的操作原就是先进先出的,又称作FIFO 表（ First In First Out ） . 队列也有次序储备和链式储备两种储备结构.队列的基本运算有六种：·置空队：InitQueue（ Q）·判队空：QueueEmpty（Q）·判队满：QueueFull （Q）可编辑资料 - - - 欢迎下载精品_精品资料_·入队：EnQueue （Q,x）·出队：DeQueue （Q）·取队头元素：QueueFront（Q）次序队列的“假上溢”现象：由于头尾指针不断前移,超出向量空间.这时整个向量空间及队列是空的却产生了“上溢”现象.为了克服“假上溢”现象引入循环向量的概念,是把向量空间形成一个头尾相接的环形,这时队列称循环队列.判定循环队列是空仍是满,方法有三种：·一种是另设一个布尔变量来判定.·其次种是少用一个元素空间,入队时先测试（ rear+1 ）%m = front）？ 满：空.·第三种就是用一个计数器记录队列中的元素的总数.队列的链式储备结构称为链队列,一个链队列就是一个操作受限的单链表.为了便于在表尾进行插入（入队）的操作,在表尾增加一个尾指针,一个链队列就由一个头指针和一个尾指针唯独的确定.链队列不存在队满和上溢的问题.在链队列的出队算法中,要留意当原队中只有一个结点时,出队后要同进修改头尾指针并使队列变空.第四章 串串是零个或多个字符组成的有限序列.·空串：是指长度为零的串,也就是串中不包含任何字符（结点） .·空白串：指串中包含一个或多个空格字符的串.·在一个串中任意个连续字符组成的子序列称为该串的子串,包含子串的串就称为主串.·子串在主串中的序号就是指子串在主串中首次显现的位置.·空串是任意串的子串,任意串是自身的子串.串分为两种： ·串常量在程序中只能引用不能转变.·串变量的值可以转变.串的基本运算有： ·求串长strlen （ char*s ）·串复制strcpy （char*to ,char*from ）·串联接strcat （char*to ,char*from）·串比较charcmp （char*s1 ,char*s2 ）·字符定位strchr （char*s , charc ）串是特别的线性表（结点是字符） ,所以串的储备结构与线性表的储备结构类似.串的次序储备结构简称为次序串.次序串又可按储备安排的不同分为：·静态储备安排：直接用定长的字符数组来定义.优点是涉及串长的操作速度快,但不适合插入、链接操作.·动态储备安排：是在定义串时不安排储备空间,需要使用时按所需串的长度安排储备单元.可编辑资料 - - - 欢迎下载精品_精品资料_串的链式储备就是用单链表的方式储备串值,串的这种链式储备结构简称为链串.链串与单链表的差异只是它的结点数据域为单个字符.为明白决“储备密度”低的状况,可以让一个结点储备多个字符,即结点的大小.次序串上子串定位的运算：又称串的“模式匹配”或“串匹配”,是在主串中查找出子串显现的位置.在串匹配中,将主串称为目标（串）,子串称为模式（串） .这是比较简洁懂得的,串匹配问题就是找出给定模式串P 在给定目标串 T 中首次显现的有效位移或者是全部有效位移.最坏的情形下时间复杂度是O（ n-m+1）m ）,假如 m 与 n 同阶的话就它是 O（ n2 ）.链串上的子串定位运算位移是结点的址而不是整数第五章 多维数组数组一般用次序储备的方式表示.储备的方式有： ·行优先次序,也就是把数组逐行依次排列. PASCAL、C·列优先次序,就是把数组逐列依次排列. FORTRAN的址的运算方法： ·按行优先次序排列的数组： LOCa （ij ）=LOCa （ 11 ）+ （ i-1 ）*n+ （j-1 ） *d.·按列优先次序排列的数组： LOCa （ij ）=LOCa （ 11 ）+ （ j-1 ）*n+ （i-1 ） *d.矩阵的压缩储备：为多个相同的非零元素安排一个储备空间.对零元素不安排空间.特别矩阵的概念：所谓特别矩阵是指非零元素或零元素分布有肯定规律的矩阵.稀疏矩阵的概念：一个矩阵中如其非零元素的个数远远小于零元素的个数,就该矩阵称为稀疏矩阵.特别矩阵的类型： ·对称矩阵：满意a（ij ）=a （ji ）.元素总数 n（n+1 ）/2.I=max （i,j）,J=min （i, j）,LOCa（ij ）=LOC（sa0 ）+ （I* （ I+1 ）/2+J ）*d.·三角矩阵： ·上三角阵：k=i* （ 2n-i+1 ）/2+j-i,LOCa（ ij ） =LOC （sa0 ） +k*d.·下三角阵：k=i* （i+1 ）/2+j , LOCa（ij ）=LOC （sa0 ）+k*d.·对角矩阵：k=2i+j,LOCa （ij ）=LOC （ sa0 ）+k*d.稀疏矩阵的压缩储备方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起,用这些结点组成的一个线性表来表示.但这种压缩储备方式将失去随机储备功能.加入行表记录每行的非零元素在三元组表中的起始位置,即带行表的三元组表.第六章 树树是 n 个结点的有限集合,非空时必需满意：只有一个称为根的结点.其余结点形成m 个不相交的子集,并称根的子树.根是开头结点.结点的子树数称度.度为0 的结点称叶子（终端结点） .度不为 0 的结点称分支结点（非终端结点）.除根外的分支结点称内部结点.有序树是子树有左,右之分的树.无序树是子树没有左,右之分的树.森林是m 个互不相交的树的集合.可编辑资料 - - - 欢迎下载精品_精品资料_树的四种不同表示方法： ·树形表示法.·嵌套集合表示法.·凹入表示法·广义表表示法.二叉树的定义：是 n 0 个结点的有限集,它是空集（ n=0 ）或由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成.二叉树不是树的特别情形,与度数为2 的有序树不同.二叉树的 4 个重要性质： ·二叉树上第i 层上的结点数目最多为 2 （ i-1 ）（i1）.·深度为k 的二叉树至多有（ 2k ）-1 个结点（ k 1）.·在任意一棵二叉树中,如终端结点的个数为 n0 ,度为 2 的结点数为 n2 ,就 n0=n2+1.·具有n 个结点的完全二叉树的深度为 int （log2n ） +1.满二叉树是一棵深度为 k,结点数为（ 2k ） -1 的二叉树.完全二叉树是满二叉树在最下层自右向左去处部分结点. 二叉树的次序储备结构就是把二叉树的全部结点依据层次次序储备到连续的储备单元中.（储备前先将其画成完全二叉树）树的储备结构多用的是链式储备. BinTNode的结构为 lchild|data|rchild,把全部 BinTNode类型的结点,加上一个指向根结点的BinTree 型头指针就构成了二叉树的链式储备结构,称为二叉链表.它就是由根指针root唯独确定的.共有 2n 个指针域, n+1 个空指针.依据拜访结点的次序不同可得三种遍历：先序遍历（前序遍历或先根遍历）,中序遍历（或中根遍历） 、后序遍历（或后根遍历）.时间复杂度为 O（n ）.利用二叉链表中的 n+1 个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针,这些附加的指针就称为“线索”,加上线索的二叉链表就称为线索链表.线索使得查找中序前趋和中序后继变得简洁有效,但对于查找指定结点的前序前趋和后序后继并没有什么作用.树和森林及二叉树的转换是唯独对应的.转换方法： ·树变二叉树：兄弟相连,保留长子的连线.·二叉树变树：结点的右孩子与其双亲连.·森林变二叉树：树变二叉树,各个树的根相连.树的储备结构：·有双亲链表表示法：结点 data | parent,对于求指定结点的双亲或祖先非常便利,但不适于求指定结点的孩子及后代.·孩子链表表示法：为树中每个结点 data | next设置一个孩子链表 firstchild,并将 data | firstchild存放在一个向量中.·双亲孩子链表表示法：将双亲链表和孩子链表结合.·孩子兄弟链表表示法：结点结构 leftmostchild |data | rightsibing,附加两个分别指向该结点的最左孩子和右邻兄弟的指针域.树的前序遍历与相对应的二叉树的前序遍历一样.树的后序遍历与相对应的二叉树的中序遍历一样.树的带权路径长度是树中全部叶结点的带权路径长度之和.树的带权路径长度最小的二叉树就称为最优二叉树（即哈夫曼树）.可编辑资料 - - - 欢迎下载精品_精品资料_在叶子的权值相同的二叉树中,完全二叉树的路径长度最短.哈夫曼树有 n 个叶结点,共有 2n-1 个结点,没有度为 1 的结点,这类树又称为严格二叉树.变长编码技术可以使频度高的字符编码短,而频度低的字符编码长,但是变长编码可能使解码产生二义性.如00 、01 、0001 这三个码无法在解码时确定是哪一个,所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀,这种码称为前缀码（其实是非前缀码） .哈夫曼树的应用最广泛的是在编码技术上,它能够简洁的求出给定字符集及其概率分布的最优前缀码.哈夫曼编码的构造很简洁, 只要画好了哈夫曼树,按分支情形在左路径上写代码0,右路径上写代码 1,然后从上到下到叶结点的相应路径上的代码的序列就是该结点的最优前缀码.第七章 图图的规律结构特点就是其结点（顶点）的前趋和后继的个数都是没有限制的,即任意两个结点之间之间都可能相关.图 GraphG= （V,E）,V 是顶点的有穷非空集合, E 是顶点偶对的有穷集.有向图 Digraph ：每条边有方向.无向图 Undigraph：每条边没有方向.有向完全图：具有 n* （n-1 ）条边的有向图.无向完全图：具有n* （n-1 ）/2 条边的无向图.有根图：有一个顶点有路径到达其它顶点的有向图.简洁路径：是经过顶点不同的路径.简洁回路是开头和终端重的简洁路径.网络：是带权的图.图的储备结构：·邻接矩阵表示法：用一个 n 阶方阵来表示图的结构是唯独的,适合稠密图.·无向图：邻接矩阵是对称的.·有向图：行是出度,列是入度.建立邻接矩阵算法的时间是 O（n+n2+e）,其时间复杂度为 O（n2 ）·邻接表表示法：用顶点表和邻接表构成不是唯独的,适合稀疏图.·顶点表结构vertex | firstedge,指针域存放邻接表头指针.·邻接表：用头指针确定. ·无向图称边表.·有向图又分出边表和逆邻接表.·邻接表结点结构为 adjvex | next,时间复杂度为 O（ n+e ）.,空间复杂度为 O（n+e ）.图的遍历： ·深度优先遍历：借助于邻接矩阵的列.使用栈储存已拜访结点.·广度优先遍历：借助于邻接矩阵的行.使用队列储存已拜访结点.生成树的定义：如从图的某个顶点动身,可以系统的拜访到图中全部顶点,就遍历时经过的边和图的全部顶点构成的子图称作该图的生成树.可编辑资料 - - - 欢迎下载精品_精品资料_最小生成树：图的生成树不唯独,从不同的顶点动身可得到不同的生成树,把权值最小的生成树称为最小生成树（MST ）.构造最小生成树的算法：·Prim 算法的时间复杂度为 O（n2 ）与边数无关适于稠密图.·Kruskal 算法的时间复杂度为 O（lge ）,主要取决于边数,较适合于稀疏图. 最短路径的算法：·Dijkstra算法,时间复杂度为 O （n2 ）.·类似于prim算法.拓扑排序：是将有向无环图 G 中全部顶点排成一个线性序列,如 <u ,v> E（G）,就在线性序列 u 在 v 之前,这种线性序列称为拓扑序列.拓扑排序也有两种方法：·无前趋的顶点优先,每次输出一个无前趋的结点并删去此结点及其出边,最终得到的序列即拓扑序列.·无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边,最终得到的序列是逆拓扑序列.第八章 排序记录中可用某一项来标识一个记录,就称为关键字项,该数据项的值称为关键字.排序是使文件中的记录按关键字递增（或递减）次序排列起来.·基本操作：比较关键字大小.转变指向记录的指针或移动记录.·储备结构：次序结构、链表结构、索引结构.经过排序后这些具有相同关键字的记录之间的相对次序保持不变,就称这种排序方法是稳固的,否就排序算法是不稳固的.排序过程中不涉及数据的内、外存交换就称之为“内部排序”（内排序）,反之,如存在数据的内外存交换,就称之为外排序.内部排序方法可分五类：插入排序、挑选排序、交换排序、归并排序和安排排序.评判排序算法好坏的标准主要有两条：执行时间和所需的帮助空间,另外算法的复杂程序也是要考虑的一个因素.插入排序：·直接插入排序： ·逐个向前插入到合适位置.·哨兵（监视哨）有两个作用： ·作为临变量存放Ri·是在查找循环中用来监视下标变量 j 是否越界.·直接插入排序是就的的稳固排序.时间复杂度为 O（ n2 ）,比较次数为（ n+2 ）（ n-1 ）/2 .移动次数为（ n+4 ）（n-1 ）/2 .·希尔排序：·等间隔的数据比较并按要求次序排列,最终间隔为 1.·希尔排序是就的的不稳固排序.时间复杂度为 O（n1.25）,比较次数为（ n1.25 ）.移动次数为（ 1.6n1.25）.交换排序：·冒泡排序：·自下向上确定最轻的一个.·自上向下确定最重的一个.·自下向上确定最轻的一个,后自上向下确定最重的一个.·冒泡排序是就的的稳固排序.时间复杂度为 O（n2 ）,比较次数为 n（ n-1 ）/2 .移动次数为 3n （n-1 ）/2 .·快速排序：·以第一个元素为参考基准,设定、动两个指针,发生交换后指针交换位置,直到指针重合.重复直到排序完成.·快速排序是非就的的不稳固排序.时间复杂度为 O（ nlog2n ）,比较次数为 n（n-1 ）/2 .挑选排序：·直接挑选排序： ·挑选最小的放在比较区前.·直接挑选排序就的的不稳固排序.时间复杂度为 O（ n2 ）.比较次数为 n（n-1 ）/2 .可编辑资料 - - - 欢迎下载精品_精品资料_·堆排序 ·建堆：按层次将数据填入完全二叉树,从 int （ n/2 ）处向前逐个调整位置.·然后将树根与最终一个叶子交换值并断开与树的连接并重建堆,直到全断开.·堆排序是就的不稳固的排序,时间复杂度为 O（nlog2n ）,不相宜于记录数较少的文件.归并排序： ·先两个一组排序,形成（n+1 ）/2 组,再将两组并一组,直到剩下一组为止.·归并排序是非就的稳固排序,时间复杂度是 O（nlog2n ）,安排排序：·箱排序：·按关键字的取值范畴确定箱子数,按关键字投入箱子,链接全部非空箱.·箱排序的平均时间复杂度是线性的 O（ n ）.·基数排序：·从低位到高位依次对关键字进行箱排序.·基数排序是非就稳固的排序,时间复杂度是 O（d*n+d*rd）.各种排序方法的比较和挑选：·待排序的记录数目n.n 较大的要用时间复杂度为 O（nlog2n ）的排序方法.·记录的大小（规模）.记录大最好用链表作为储备结构,而快速排序和堆排序在链表上难于实现.·关键字的结构及其初始状态.·对稳固性的要求.·语言工具的条件.·储备结构.·时间和帮助空间复杂度.第九章 查找查找的同时对表做修改操作（如插入或删除）就相应的表称之为动态查找表,否就称之为静态查找表.衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数（即平均查找长度ASL）.线性表查找的方法： ·次序查找：逐个查找,ASL= （ n+1 ）/2 .·二分查找：取中点int （n/2 ）比较,如小就比左区间,大就比右区间.用二叉判定树表示.ASL= （每层结点数* 层数） /N.·分块查找.要求“分块有序”,将表分成如干块内部不肯定有序,并抽取各块中的最大关键字及其位置建立有序索引表.二叉排序树（ BST）定义是：二叉排序树是空树或者满意如下性质的二叉树：·如它的左子树非空,就左子树上全部结点的值均小于根结点的值.·如它的右子树非空,就右子树上全部结点的值均大于根结点的值.·左、右子树本身又是一棵二叉排序树.二叉排序树的插入、建立、删除的算法平均时间性能是O（nlog2n ）.二叉排序树的删除操作可分三种情形进行处理：·*P 是叶子,就直接删除 *P,即将 *P 的双亲 *parent中指向 *P 的指针域置空即可.·*P 只有一个孩子 *child ,此时只需将 *child 和*p 的双亲直接连接就可删去 *p.·*p 有两个孩子,就先将 *p 结点的中序后继结点的数据到 *p ,删除中序后继结点.关于 B- 树（多路平稳查找树） .它适合在磁盘等直接存取设备上组织动态的查找表,是一种外查找算法.建立的方式是从下向上拱起.散列技术：将结点按其关键字的散列的址储备到散列表的过程称为散列.散列函数的挑选有两条标准：简洁和匀称.常见的散列函数构的造方法：·平方取中法：hash=int（ x2 ）%100 ）可编辑资料 - - - 欢迎下载精品_精品资料_·除余法：表长为m ,hash=x%m·相乘取整法：hash=int（m* （x*A-int （x*A）. A=0.618·随机数法：hash=random（ x）.处理冲突的方法：·开放定址法： ·一般形式为hi= （h（key ）+di ）%m1 im-1 ,开放定址法要求散列表的装填因子 1.·开放定址法类型： ·线性探查法：address= （ hash （x）+i ） %m .·二次探查法：address= （hash （x）+i2 ）%m .·双重散列法：address= （hash （x）+i*hash （ y） %m .·拉链法：·是将全部关键字为同义词的结点链接在同一个单链表中.·拉链法的优点： ·拉链法处理冲突简洁,且无积累现象.·链表上的结点空间是动态申请的适于无法确定表长的情形.·拉链法中可以大于1,结点较大时其指针域可忽视,因此节约空间.·拉链法构造的散列表删除结点易实现.·拉链法也有缺点：当结点规模较小时,用拉链法中的指针域也要占用额外空间,仍是开放定址法省空间.第十章 排序10.1 排序的基本概念10.2 插入排序10.3 挑选排序10.4 交换排序本章主要学问点：排序的基本概念和衡量排序算法优劣的标准,其中衡量标准有算法的时间复杂度、空间复杂度和稳固性直接插入排序,希尔排序直接挑选排序,堆排序冒泡排序,快速排序10.1 排序的基本概念1. 排序是对数据元素序列建立某种有序排列的过程.2. 排序的目的：便于查找.3. 关键字是要排序的数据元素集合中的一个域,排序是以关键字为基准进行的.关键字分主关键字和次关键字两种. 对要排序的数据元素集合来说, 假如关键字满意数据元素值不同时该关键字的值也肯定不同, 这样的关键字称为主关键字.不满意主关键字定义的关键字称为次关键字.4. 排序的种类：分为内部排序和外部排序两大类.如待排序记录都在内存中,称为内部排序.如待排序记录一部分在内存,一部分在外存,就称为外部排序.可编辑资料 - - - 欢迎下载精品_精品资料_注：外部排序时,要将数据分批调入内存来排序,中间结果仍要准时放入外存,明显外部排序要复杂得多.5. 排序算法好坏的衡量标准：(1) 时间复杂度 它主要是分析记录关键字的比较次数和记录的移动次数.(2) 空间复杂度算法中使用的内存帮助空间的多少.(3) 稳固性如两个记录 A 和 B 的关键字值相等,但排序后 A、B 的先后次序保持不变,就称这种排序算法是稳固的.10.2 插入排序插入排序的基本思想是：每步将一个待排序的对象,按其关键字大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止.简言之,边插入边排序,保证子序列中随时都是排好序的.常用的插入排序有：直接插入排序和希尔排序两种.10.2.1 直接插入排序1、其基本思想是：次序的把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置.例 1 ：关键字序列 T= （13 ,6 ,3 ,31 ,9,27 ,5 ,11 ）,请写出直接插入排序的中间过程序列.初始关键字序列：【13 】, 6, 3, 31, 9, 27, 5, 11第一次排序：【6, 13 】, 3, 31, 9, 27, 5, 11其次次排序：【3, 6, 13 】, 31, 9, 27, 5, 11第三次排序：【3, 6, 13 , 31 】, 9, 27, 5, 11第四次排序：【3, 6, 9, 13 ,31 】, 27, 5, 11第五次排序：【3, 6, 9, 13 ,27, 31 】, 5, 11第六次排序：【3, 5, 6, 9, 13 , 27, 31 】, 11第七次排序：【3, 5, 6, 9, 11 , 13 , 27, 31 】注：方括号 中为已排序记录的关键字,下划横线的关键字表示它对应的记录后移一个位置.2.直接插入排序算法public static void insertSortint a int i, j, temp;int n = a.Length;fori = 0; i < n - 1; i +temp = ai + 1;可编辑资料 - - - 欢迎下载精品_精品资料_j = i;whilej > -1 && temp < aj aj + 1 = aj;j -;aj + 1 = temp;初始关键字序列：【13 】, 6, 3, 31, 9, 27, 5, 11第一次排序：【6, 13 】, 3, 31, 9, 27, 5, 11其次次排序：【3, 6, 13 】, 31, 9, 27, 5, 113、直接插入排序算法分析(1) 时间效率：当数据有序时, 执行效率最好, 此时的时间复杂度为 On .当数据基本反序时, 执行效率最差, 此时的时间复杂度为 On2 .所以当数据越接近有序,直接插入排序算法的性能越好.(2) 空间效率：仅占用 1 个缓冲单元 O （1）(3) 算法的稳固性：稳固8.2.2 希尔（ shell ）排序 （又称缩小增量排序）1、基本思想：把整个待排序的数据元素分成如干个小组,对同一小组内的数据元素用直接插入法排序.小组的个数逐次缩小,当完成了全部数据元素都在一个组内的排序后排序过程终止.2 、技巧：小组的构成不是简洁的“逐段分割”,而是将相隔某个增量 d 的记录组成一个小组 ,让增量 d 逐趟缩短（例如依次取 5,3,1 ）,直到 d 1 为止.3、优点：让关键字值小的元素能很快前移,且序列如基本有序时,再用直接插入排序处理,时间效率会高许多.例 2 ：设待排序的序列中有 12 个记录,它们的关键字序列T=65 ,34 ,25 ,87 ,12 ,38 , 56 , 46 ,14 ,77 ,92 ,23 ）,请写出希尔排序的详细实现过程.public static void shellSortint a, int d, int numOfD int i, j, k, m, span;int temp;int n = a.Length;form = 0; m < numOfD; m + /共 numOfD次循环span = dm;/ 取本次的增量值fork = 0; k < span; k +/ 共 span 个小组fori = k; i < n-span; i = i + span temp = ai+span;可编辑资料 - - - 欢迎下载精品_精品资料_j = i;whilej > -1 && temp < aj aj + span = aj;j = j - span;aj + span = temp;算法分析：开头时 d的值较大,子序列中的对象较少,排序速度较快.随着排序进展,d值逐步变小,子序列中对象个数逐步变多,由于前面工作的基础,大多数记录已基本有序,所以排序速度仍旧很快.时间效率： Onlog2n2空间效率： O（1）由于仅占用 1 个缓冲单元算法的稳固性：不稳固练习：1.欲将序列（ Q, H, C, Y, P, A, M, S, R, D, F, X ）中的关键码按字母升序重排,就初始d 为 4 的希尔排序一趟的结果是？ 答： 原始序列：Q, H, C, Y, P, A, M, S, R, D, F,Xshell 一趟后： P,A,C,S,Q,D,F,X,R,H,M,Y2. 以关键字序列（ 256 ,301 , 751 ,129 ,937 , 863 ,742 ,694 ,076 ,438 ）为例,写出执行希尔排序（取d=5,3,1 ）算法的各趟排序终止时,关键字序列的状态.解：原始序列 : 256 ,301 ,751 ,129 , 937 ,863 ,742 ,694 ,076 , 438希尔排序第一趟 d=5256301694076438863742751129937其次趟 d=3076301129256438694742751863937第三趟 d=107612925630143869474275186393710.3 挑选排序挑选排序的基本思想是： 每次从待排序的数据元素集合中选取关键字最小（或最大） 的数据元素放到数据元素集合的最前 （或最终）, 数据元素集合不断缩小,当数据元素集合为空时挑选排序终止.常用的挑选排序算法：（1） ）直接挑选排序