严蔚敏数据结构复习完整版.doc

1. 复杂性分析对各种操作的时间复杂性的分析。 主要是链表，树，排序等简单一些的分析。分析的时候，从简单的入手，学会方法。后续的各种豆可能让你分析时间复杂度。 线性链表（顺序表和单链表） 链表 循环链表 双向链表2. 线性结构 队列（循环队列） 栈链表主要操作：找某一个元素，插入一个（在哪个位置增加），删除一个（在哪个位置删除）。栈：查找，插入（位置固定），删除（位置固定）队列：查找，插入（位置固定），删除（位置固定）顺序表（可以视为一个数组）单链表：（删除）（插入）倒置：（查找）循环链表双向链表栈：（插入删除查找）队列（插入删除查找）循环队列的实现，并不是像上面的图那样，实现了一个循环的样子。3. 二叉树基本概念二叉树是每个节点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；2. 树的结点无左、右之分，而二叉树的结点有左、右之分。二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：(1)空二叉树如图(a)；(2)只有一个根结点的二叉树如图(b)；(3)只有左子树如图(c)；(4)只有右子树如图(d)；(5)完全二叉树如图(e)注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形性质(1) 在非空二叉树中，第i层的结点总数不超过, i=1；(2) 深度为h的二叉树最多有2h-1个结点(h=1)，最少有h个结点；(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；(4) 具有n个结点的完全二叉树的深度为(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若I为结点编号则 如果I1，则其父结点的编号为I/2；如果2*IN，则无左儿子；如果2*I+1N，则无右儿子。(6)给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。（7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i 存储结构顺序存储表示二叉树可以用数组或线性表来存储，而且如果这是满二叉树，这种方法不会浪费空间。用这种紧凑排列，如果一个结点的索引为i，它的子结点能在索引2i+1和2i+2找到，并且它的父节点（如果有）能在索引floor(i-1)/2)找到（假设根节点的索引为0）。这种方法更有利于紧凑存储和更好的访问的局部性，特别是在前序遍历中。然而，它需要连续的存储空间，这样在存储高度为h的n个结点组成的一般普通树时将会浪费很多空间。一种最极坏的情况下如果深度为h的二叉树每个节点只有右孩子需要占用2的h次幂减1，而实际却只有h个结点，空间的浪费太大，这是顺序存储结构的一大缺点。 /* 二叉树的顺序存储表示 */ #define MAX_TREE_SIZE 100 /* 二叉树的最大节点数 */ typedef TElemType SqBiTreeMAX_TREE_SIZE; /* 0号单元存储根节点 */ typedef struct int level,order; /* 节点的层，本层序号(按满二叉树计算) */ position;二叉链表存储表示/* 二叉樹的二叉鏈表存儲表示 */ typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指針 */ BiTNode,*BiTree;遍历算法二叉树的遍历三种方式，如下：（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。 （3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。 例1：如上图所示的二叉树，若按前序遍历，则其输出序列为 。若按中序遍历，则其输出序列为 。若按后序遍历，则其输出序列为 。前序：根A，A的左子树B，B的左子树没有，看右子树，为D，所以A-B-D。再来看A的右子树，根C，左子树E，E的左子树F，E的右子树G，G的左子树为H，没有了结束。连起来为C-E-F-G-H,最后结果为ABDCEFGH中序：先访问根的左子树,B没有左子树，其有右子树D，D无左子树，下面访问树的根A，连起来是BDA。再访问根的右子树，C的左子树的左子树是F，F的根E，E的右子树有左子树是H，再从H出发找到G，到此C的左子树结束，找到根C，无右子树，结束。连起来是FEHGC, 中序结果连起来是BDAFEHGC后序：B无左子树，有右子树D，再到根B。再看右子树，最下面的左子树是F，其根的右子树的左子树是H，再到H的根G，再到G的根E，E的根C无右子树了，直接到C，这时再和B找它们其有的根A，所以连起来是DBFHGECA 深度优先遍历在深度优先中，我们希望从根结点访问最远的结点。和图的深度优先搜索不同的是，不需记住访问过的每一个结点，因为树中不会有环。广度优先遍历和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。完全二叉树，满二叉树1. 满二叉树：一棵深度为k，且有个节点称之为满二叉树2. 完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树4. 树基本概念树（tree）是包含n（n0）个结点的有穷集，其中：（1）每个元素称为结点（node）；（2）有一个特定的结点被称为根结点或树根（root）。（3）除根结点之外的其余数据元素被分为m（m0）个互不相交的集合T1，T2，Tm-1，其中每一个集合Ti（1=i=0）棵互不相交的树的集合称为森林；存储父节点表示法/* 树节点的定义 */#define MAX_TREE_SIZE 100typedef struct TElemType data; int parent; /* 父节点位置域 */ PTNode;typedef struct PTNode nodesMAX_TREE_SIZE; int n; /* 节点数 */ PTree;孩子链表表示法/*树的孩子链表存储表示*/typedef struct CTNode / 孩子节点 int child; struct CTNode *next; *ChildPtr;typedef struct ElemType data； / 节点的数据元素 ChildPtr firstchild； / 孩子链表头指针 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE； int n, r； / 节点数和根节点的位置 CTree;5.森林6.森林、树与二叉树的转换将树转换为二叉树 树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：在所有兄弟结点之间加一连线；对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。注意： 由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。2）将一个森林转换为二叉树具体方法是： 将森林中的每棵树变为二叉树 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。二叉树到树、森林的转换把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。图二元组的定义图G是一个有序二元组(V,E)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与V不相交。它们亦可写成V(G)和E(G)。E的元素都是二元组，用(x,y)表示，其中x,yV。三元组的定义图G是指一个三元组(V,E,I)，其中V称为顶集，E称为边集，E与V不相交；I称为关联函数，I将E中的每一个元素映射到。如果e被映射到(u,v)，那么称边e连接顶点u,v，而u,v则称作e的端点，u,v此时关于e相邻。同时，若两条边i,j有一个公共顶点u，则称i,j关于u相邻。有/无向图如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。简单图一个图如果1. 没有两条边，它们所关联的两个点都相同（在有向图中，没有两条边的起点终点都分别相同）；2. 每条边所关联的是两个不同的顶点则称为简单图（Simple graph）。简单的有向图和无向图都可以使用以上的“二元组的定义”，但形如的序对不能属于E。而无向图的边集必须是对称的，即如果，那么。基本术语阶（Order）：图G中顶集V的大小称作图G的阶。子图（Sub-Graph）：当图G=(V,E)其中V包含于V，E包含于E，则G称作图G=(V,E)的子图。每个图都是本身的子图。生成子图（Spanning Sub-Graph）：指满足条件V(G) = V(G)的G的子图G。导出子图（Induced Subgraph）：以图G的顶点集V的非空子集V1为顶点集，以两端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图；以图G的边集E的 非空子集E1为边集，以E1中边关联的顶点的全体为顶点集的G的子图，称为E1导出的导出子图。度（Degree）：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)。入度（In-degree）和出度（Out-degree）：对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。自环（Loop）：若一条边的两个顶点为同一顶点，则此边称作自环。路径（Path）：从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,.ek,vk，其中ei的顶点为vi及vi - 1，k称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。一条路径称为一简单路径(simple path)，如果路径中除起始与终止顶点可以重合外，所有顶点两两不等。行迹（Trace）：如果路径P(u,v)中的边各不相同，则该路径称为u到v的一条行迹。轨道（Track）：如果路径P(u,v)中的顶点各不相同，则该路径称为u到v的一条轨道。闭的行迹称作回路（Circuit），闭的轨称作圈（Cycle）。（另一种定义是：walk对应上述的path，path对应上述的track。Trail对应trace。）桥（Bridge）：若去掉一条边，便会使得整个图不连通，该边称为桥。图的存储表示1. 数组（邻接矩阵）存储表示（有向或无向）2. 邻接表存储表示邻接表是图的一种链式存储结构。邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。邻接表中的表结点和头结点结构：有向图的邻接表和逆邻接表（一）在有向图的邻接表中，第i个单链表链接的边都是顶点i发出的边。（二）为了求第i个顶点的入度，需要遍历整个邻接表。因此可以建立逆邻接表。（三）在有向图的逆邻接表中，第i个单链表链接的边都是进入顶点i的边。邻接表小结设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个顶点结点，2e个表结点；用邻接表表示有向图时，若不考虑逆邻接表，只需n个顶点结点，e个边结点。在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数。在有向图中，第i个链表中的结点个数只是顶点vi的出度。在逆邻接表中的第i个链表中的结点个数为vi的入度。建立邻接表的时间复杂度为O(n+e)。3. 有向图的十字链表存储表示十字链表表示特点1.针对弧结点，增加入弧链表结构和出弧链表结构；2.容易求得任意顶点的出度和入度，专用于有向图的操作；3.结构实现比较复杂。4.无向图的邻接多重表存储表示邻接多重表(Adjacency Multilist)主要用于存储无向图。因为，如果用邻接表存储无向图，每条边的两个边结点分别在以该边所依附的两个顶点为头结点的链表中，这给图的某 些操作带来不便。例如，对已访问过的边做标记，或者要删除图中某一条边等，都需要找到表示同一条边的两个结点。因此，在进行这一类操作的无向图的问题中采 用邻接多重表作存储结构更为适宜。邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如图其中，顶点表由两个域组成，vertex 域存储和该顶点相关的信息firstedge 域指示第一条依附于该顶点的边；边表结点由六个域组成，mark 为标记域，可用以标记该条边是否被搜索过；ivex 和jvex 为该边依附的两个顶点在图中的位置；ilink 指向下一条依附于顶点ivex的边;jlink 指向下一条依附于顶点jvex 的边，info 为指向和边相关的各种信息的指针域。一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图(网)，相应位置为。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶点建立一个单链表（并按建立的次序编号），第i个单链表中 的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧）。每个结点由两个域组成：邻接点域(adjvex)，用以指示与vi邻接的点在图中的位 置，链域(nextarc)用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域 （info）。每个顶点的单链表中结点的个数即为该顶点的出度(与该顶点连接的边的总数)。无论是存储图或网，都需要在每个单链表前设一表头结点，这些表 头结点的第一个域data用于存放结点vi的编号i，第二个域firstarc用于指向链表中第一个结点。在上面两个图结构中，一个是有向图，即每条边都有方向，另一个是无向图，即每条边都没有方向。在有向图中，通常将边称作弧，含箭头的一端称为弧头，另一端称为弧尾，记作，它表示从顶点vi到顶点vj有一条边。若有向图中有n个顶点，则最多有n(n-1)条弧，我们又将具有n(n-1)条弧的有向图称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度，以顶点v为弧头的弧的数目称作顶点v的入度。在无向图中，边记作(vi,vj)，它蕴涵着存在和两条弧。若无向图中有n个顶点，则最多有n(n-1)/2条弧，我们又将具有n(n-1)/2条弧的无向图称作无向完全图。与顶点v相关的边的条数称作顶点v的度。路径长度是指路径上边或弧的数目。若第一个顶点和最后一个顶点相同，则这条路径是一条回路。若路径中顶点没有重复出现，则称这条路径为简单路径。在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。图的遍历图的遍历方法有深度优先搜索法和广度（宽度）优先搜索法。深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的 顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被 访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻 接点vi1,vi2, vi t，并均标记已访问过，然后再按照vi1,vi2, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。图的连通性问题无向图的连通分量和生成树有向图的强连通分量最小生成树边赋以权值的图称为网或带权图，带权图的生成树也是带权的，生成树T各边的权值总和称为该树的权。 最小生成树（MST）：权值最小的生成树。 生成树和最小生成树的应用：要连通n个城市需要n1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。 构造网的最小生成树必须解决下面两个问题： 1、尽可能选取权值小的边，但不能构成回路； 2、选取n1条恰当的边以连通n个顶点； MST性质：假设G(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中uU，vVU，则必存在一棵包含边(u,v)的最小生成树。 1.prim算法 基本思想：假设G(V，E)是连通的，TE是G上最小生成树中边的集合。算法从Uu0（u0V）、TE开始。重复执行下列操作： 在所有uU，vVU的边(u，v)E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到VU为止。 此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。 Prim算法的核心:始终保持TE中的边集构成一棵生成树。注意：prim算法适合稠密图，其时间复杂度为O(n2)，其时间复杂度与边得数目无关，而kruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。看了上面一大段文字是不是感觉有点晕啊，为了更好理解我在这里举一个例子，示例如下：大家可能已经看出来了，kruskal算法寻找安全边的方式，就是在所有的边中找最小的表，只要两个节点是两个不相交集合，就加入到最小生成树中，直到所有的节点都连接起来。有向无环图关键路径最短路径迪杰斯特拉算法Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对 应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包 含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。例如，对下图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下表中。先给出一个无向图用Dijkstra算法找出以A为起点的单源最短路径步骤如下弗洛伊德算法1.定义概览Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。2.算法描述1)算法思想原理： Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在） 从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) right一定不为空，右旋的时候p-left一定不为空，这是显而易见的。如果从空树开始建立，并时刻保持平衡，那么不平衡只会发生在插入删除操作上，而不平衡的标志就是出现bf = 2或者bf = -2的节点。删除虽然平衡二叉树的节点删除操作的代码比较复杂，代码量也比较大，但是其删除过程只有以下3种情况：注：只要牢牢把握住以下3点，理解平衡二叉树的删除操作不是太难 被删的节点是叶子节点处理思路：将该节点直接从树中删除，并利用递归的特点和高度的变化，反向推算其父节点和祖先节点是否失衡。如果失衡，则判断是那种类型的失衡（LL、LR、RR、RL），再对失衡节点进行旋转处理，直到根节点或高度不再变化。 被删的节点只有左子树或只有右子树处理思路：将左子树（右子树）替代原有节点的位置，并利用递归的特点和高度的变化，反向推算父节点和祖先节点是否失衡。如果失衡，则判断是那种类型的失衡（LL、LR、RR、RL），再对失衡节点进行旋转处理，直到根节点或高度不再发生变化。 被删的节点既有左子树又有右子树处理思路：找到被删节点的左子树的最右端的节点rnode，将rnode的值赋给node，再把rnode的左孩子替换rnode的位置，在把rnode 释放掉，并利用递归特点，反向推断rnode的父节点和祖父节点是否失衡。如果失衡，则判断是哪种类型的失衡（LL、LR、RR、RL），再对失衡的节点 进行旋转处理，直到根节点或高度不再发生变化。B-树和B+树定义和分析，算法要求程度不高。哈希表定义构造方法处理冲突的方法查找排序插入排序直接插入排序1直接插入排序的基本思想 直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。设数组为a0n-1。1.初始时，a0自成1个有序区，无序区为a1.n-1。令i=12.将ai并入当前的有序区a0i-1中形成a0i的有序区间。3.i+并重复第二步直到i=n-1。排序完成。折半插入排序算法的基本过程： 1）计算0i-1的中间点，用i索引处的元素与中间值进行比较，如果i索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半； 2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为1/21/41/8.快速的确定出第i 个元素要插在什么地方； 3）确定位置之后，将整个序列后移，并将元素插入到相应位置。2路插入排序表插入排序希尔排序该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组 成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插 入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组 的第几个元素， 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)这样每组排序后就变成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。快速排序冒泡排序冒泡排序算法的运作如下：（从后往前）比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。快速排序是对冒泡排序的一种改进快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采 用，再加上快速排序思想-分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考 试如软考，考研中也常常出现快速排序的身影。总的说来，要直接默写出快速排序还是有一定难度的，因为本人就自己的理解对快速排序作了下白话解释，希望对大家理解有帮助，达到快速排序，快速搞定。快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。该方法的基本思想是：1先从数列中取出一个数作为基准数。2分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。3再对左右区间重复第二步，直到各区间只有一个数。初始时，i = 0; j = 9; X = ai = 72由于已经将a0中的数保存到X中，可以理解成在数组a0上挖了个坑，可以将其它数据填充到这来。从 j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a8挖出再填到上一个坑a0中。a0=a8; i+; 这样一个坑a0就被搞定了，但又形成了一个新坑a8，这怎么办了？简单，再找数字来填a8这个坑。这次从i开始向后找一个大于X的数，当 i=3，符合条件，将a3挖出再填到上一个坑中a8=a3; j-;再重复上面的步骤，先从后向前找，再从前向后找。从j开始向前找，当j=5，符合条件，将a5挖出填到上一个坑中，a3 = a5; i+;从i开始向后找，当i=5时，由于i=j退出。此时，i = j = 5，而a5刚好又是上次挖的坑，因此将X填入a5。可以看出a5前面的数字都小于它，a5后面的数字都大于它。因此再对a04和a69这二个子区间重复上述步骤就可以了。对挖坑填数进行总结1i =L; j = R; 将基准数挖出形成第一个坑ai。2j-由后向前找比它小的数，找到后挖出此数填前一个坑ai中。3i+由前向后找比它大的数，找到后也挖出此数填到前一个坑aj中。4再重复执行2，3二步，直到i=j，将基准数填入ai中。选择排序简单选择排序设所排序序列的记录个数为n。i取1,2,n-1,从所有n-i+1个记录（Ri,Ri+1,Rn）中找出排序码最小的记录，与第1个记录交换。执行n-1趟 后就完成了记录序列的排序。最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是(n-1)+(n-2)+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n2)，进行移动操作的时间复杂度为O(n)。简单选择排序是不稳定排序。树形选择排序堆排序1.堆堆实际上是一棵完全二叉树，其任何一非叶节点满足性质： Keyi=key2i+1&Keyi=Key2i+1&key=key2i+2 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。 堆分为大顶堆和小顶堆，满足Keyi=Key2i+1&key=key2i+2称为大顶堆，满足 Keyi=key2i+1&Keyi=key2i+2称为小顶堆。由上述性质可知大顶堆的堆顶的关键 字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。2.堆排序的思想 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。 其基本思想为(大顶堆)： 1)将初始待排序关键字序列(R1,R2.Rn)构建成大顶堆，此堆为初始的无序区； 2)将堆顶元素R1与最后一个元素Rn交换，此时得到新的无序区(R1,R2,.Rn-1)和新的有序区(Rn),且满足R1,2.n-1=Rn; 3)由于交换后新的堆顶R1可能违反堆的性质，因此需要对当前无序区(R1,R2,.Rn-1)调整为新堆，然后再次将R1与无序区最 后一个元素交换，得到新的无序区(R1,R2.Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排 序过程完成。 操作过程如下： 1)初始化堆：将R1.n构造为堆； 2)将当前无序区的堆顶元素R1同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。 因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。给定一个整形数组a=16,7,3,20,17,8，对其进行堆排序。 首先根据该数组元素构建一个完全二叉树，得到然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：20和16交换后导致16不满足堆的性质，因此需重新调整这样就得到了初始堆。即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。此时3位于堆顶不满堆的性质，则需调整继续调整继续调整：这样整个区间便已经有序了。 从上述过程可知，堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R1.n中选择最大记录，需比较n-1次，然后 从R1.n-2中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的 特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字