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

数据构造学问点概括第一章 概 论数据就是指可以被计算机识别、存储与加工处理的信息的载体。数据元素是数据的根本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。数据构造的定义：·逻辑构造：从逻辑构造上描绘数据，独立于计算机。·线性构造：一对一关系。·线性构造：多对多关系。·存储构造：是逻辑构造用计算机语言的实现。·依次存储构造：如数组。·链式存储构造：如链表。·索引存储构造：·稠密索引：每个结点都有索引项。·稀疏索引：每组结点都有索引项。·散列存储构造：如散列表。·数据运算。·对数据的操作。定义在逻辑构造上，每种逻辑构造都有一个运算集合。·常用的有：检索、插入、删除、更新、排序。数据类型：是一个值的集合以与在这些值上定义的一组操作的总称。·构造类型：由用户借助于描绘机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织与与之的操作。相当于在概念层上描绘问题。 ·优点是将数据与操作封装在一起实现了信息隐藏。程序设计的本质是对实际问题选择一种好的数据构造，设计一个好的算法。算法取决于数据构造。算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。评价算法的好坏的因素：·算法是正确的；·执行算法的时间；·执行算法的存储空间（主要是扶植存储空间）；·算法易于理解、编码、调试。时间困难度：是某个算法的时间消耗，它是该算法所求解问题规模n的函数。渐近时间困难度：是指当问题规模趋向无穷大时，该算法时间困难度的数量级。评价一个算法的时间性能时，主要标准就是算法的渐近时间困难度。算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。时间困难度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n2）、立方阶O（n3）、k次方阶O（nk）、指数阶O（2n）。空间困难度：是某个算法的空间消耗，它是该算法所求解问题规模n的函数。算法的时间困难度与空间困难度合称算法困难度。第二章 线性表线性表是由n0个数据元素组成的有限序列。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个互不相交的树的集合；树的四种不同表示方法：·树形表示法；·嵌套集合表示法；·凹入表示法·广义表表示法。二叉树的定义：是n0个结点的有限集，它是空集（n=0）或由一个根结点与两棵互不相交的分别称作这个根的左子树与右子树的二叉树组成。二叉树不是树的特殊情形，与度数为2的有序树不同。二叉树的4个重要性质： ·二叉树上第i层上的结点数目最多为2（i-1）（i1）。；·深度为k的二叉树至多有（2k）-1个结点（k1）；·在随意一棵二叉树中，若终端结点的个数为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）%m1im-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 insertSort(int a)int i, j, temp;int n = a.Length;for(i = 0; i < n - 1; i +) temp = ai + 1; j = i; while(j > -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)时间效率：当数据有序时，执行效率最好，此时的时间困难度为O(n)；当数据根本反序时，执行效率最差，此时的时间困难度为O(n2)。所以当数据越接近有序，干脆插入排序算法的性能越好。 (2)空间效率：仅占用1个缓冲单元O（1） (3)算法的稳定性：稳定8.2.2 希尔（shell）排序 （又称缩小增量排序）1、根本思想：把整个待排序的数据元素分成若干个小组，对同一小组内的数据元素用干脆插入法排序；小组的个数逐次缩小，当完成了全部数据元素都在一个组内的排序后排序过程完毕。 2、技巧：小组的构成不是简洁地“逐段分割”，而是将相隔某个增量d的记录组成一个小组,让增量d逐趟缩短（例如依次取5,3,1），直到d1为止。3、优点：让关键字值小的元素能很快前移，且序列若根本有序时，再用干脆插入排序处理，时间效率会高许多。例2：设待排序的序列中有12个记录，它们的关键字序列 T=(65，34，25，87，12，38，56，46，14，77，92，23），请写出希尔排序的详细实现过程。public static void shellSort(int a, int d, int numOfD)int i, j, k, m, span;int temp;int n = a.Length;for(m = 0; m < numOfD; m +)/共numOfD次循环span = dm; /取本次的增量值for(k = 0; k < span; k +)/共span个小组for(i = k; i < n-span; i = i + span)temp = ai+span;j = i;while(j > -1 && temp < aj)aj + span = aj;j = j - span;aj + span = temp;算法分析：开场时d 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，d 值渐渐变小，子序列中对象个数渐渐变多，由于前面工作的根底，大多数记录已根本有序，所以排序速度照旧很快。 时间效率：O(n(log2n)2) 空间效率：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=5 256 301 694 076 438 863 742 751 129 937 第二趟d=3 076 301 129 256 438 694 742 751 863 937第三趟d=1 076 129 256 301 438 694 742 751 863 93710.3 选择排序 选择排序的根本思想是：每次从待排序的数据元素集合中选取关键字最小（或最大）的数据元素放到数据元素集合的最前（或最终），数据元素集合不断缩小，当数据元素集合为空时选择排序完毕。常用的选择排序算法： （1）干脆选择排序 （2）堆排序10.3.1干脆选择排序1、其根本思想 每经过一趟比拟就找出一个最小值，与待排序列最前面的位置互换即可。（即从待排序的数据元素集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置的数据元素集合中选取关键字最小的数据元素并将它与原始数据集合中的第二个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数据元素为止。）2、优缺点优点：实现简洁缺点：每趟只能确定一个元素，表长为n时须要n-1趟例3：关键字序列T= （21，25，49，25*，16，08），请给出干脆选择排序的详细实现过程。原始序列： 21，25，49，25*，16，08第1趟 08，25，49，25*，16，21第2趟 08，16, 49，25*，25，21第3趟 08，16, 21，25*，25，49第4趟 08，16, 21，25*，25，49第5趟 08，16, 21，25*，25，49public static void selectSort(int a)int i, j, small;int temp;int n = a.Length;for(i = 0; i < n - 1; i +) small = i; /设第i个数据元素最小 for(j = i + 1; j < n; j +)/找寻最小的数据元素 if(aj < asmall) small = j; /记住最小元素的下标 if(small != i) /当最小元素的下标不为i时交换位置 temp = ai; ai = asmall; asmall = temp;3、算法分析时间效率： O(n2)虽挪动次数较少，但比拟次数仍多。 空间效率：O（1）没有附加单元（仅用到1个temp)算法的稳定性：不稳定4、稳定的干脆选择排序算法例：关键字序列T=