查找效率最高的二叉搜索树是_二叉排序树怎么构造

数据结构一些知识点 　　这个适合大一大二学数据结构的来学习，因为这是我大二学数据结构考试之前整理的。这个主要正对考试来整理的，一些填空选择等，还有一些常见的知识点。希望对你们有帮助！喜欢的话希望收藏点赞噢！ 　　一、线性顺序表和线性链表 　　1、在一个单链表中，若p所指节点不是最后节点，在p之后插入s所指节点，则执行 s->link=p->link; p->link=s; 　　2、 　　时间复杂度为 log2(n) 　　3、在相同的规模n下，复杂度O(n）的算法在时间上总是优于复杂度O(2n）的算法。对 　　所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。对 　　同一个算法，实现语言的级别越高，执行效率就越低。错 　　4、数据的存储结构通常有：顺序存储结构、链式存储结构、索引结构和散列结构 　　5、线性表逻辑结构特点是，只有一个首结点和尾结点；除首尾结点外其他结点只有一个直接前驱和一个 直接后继。简言之，线性结构反映结点间的逻辑关系是一对一（1:1）的。 　　顺序存储时，相邻数据素的存放地址也相邻（逻辑与物理统一）；要求预先开辟足够大的连续的内存空间。 　　链式存储时，相邻数据素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。结点空间可以随用随开辟。 　　顺序存储的优点是存储密度大(＝1)，存储空间利用率高。缺点是插入或删除素时不方便。 链式存储的优点是插入或删除素时很方便，使用灵活。缺点是存储密度小（<1），存储空间利用率低。 　　顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 　　6、给定具有n个素的顺序表，建立一个有序线性链表的时间复杂度为O(n * *2) 　　7、数据采用链式存储结构，要求 每个链结点占用一片地址连续的存储空间 　　8、链表不具有的特点：可随机访问任一素 　　9、链表具有的特点：插入、删除不需要移动素、不必事先估计存储空间 、所需空间与线性长度成正比 　　1-2 10、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新素的算法的时间复杂度为O(n) 　　11、某线性表中最常用的操作是在最后一个素之后插入一个素和删除第一个素，则采用仅有尾指针的单循环链表存储方式最节省运算时间。 　　12、在一个单向循环链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改 2个指针域的值 　　13、在一个具有n个链结点的线性链表中查找某一个链结点，若查找成功，需要平均比较 (n+1)/2 个链结点。 　　14、在一个以 h 为头的单循环链表中，p 指针指向链尾的条件是 p->next = h 　　1-1 15、删除非空线性链表中由q所指的链结点（其直接前驱结点由r指出）的动作时执行语句 r->link=q->link 和 free(q) 　　16、在具有n个链结点的链表中查找一个链结点的时间复杂度为O( n ） 　　17、在一个长度为n的顺序表中第i个素（1<=i<=n）之前插入一个素时，需向后移动 n-i+1 　　1-2 18、线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的素，时间复杂度为O(n)；而在链式存储方式下，插入和删除操作的时间复杂度都是 O(1) 　　19、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一素的概率相同，则删除一个素平均需要移动素的个数是 (n-1)/2 　　20、 　　二、栈和队列和串 　　1、一个栈的输入序列为1,2,3…n，若输出序列的第一个素是n，则输出第i(1<=i<=n)个素是 n-i+1 　　2、设S 为一个长度为n 的字符串，其中的字符各不相同，则S 中的互异的非平凡子串（非空且不同于S本身）的个数为 (n2/2)+(n/2)-1 　　3、串的性质：串是字符的有限序列 模式匹配是串的一种重要运算 串既可以采用顺序存储，也可以采用链式存储 　　4、串的长度是指 串中所含字符的个数 　　5、设栈S和队列Q的初始状态均为空，素a,b,c,d,e, f,g依次进入栈S。若每个素出栈后立即进入队列Q,且7个素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是 3 根据栈先进后出和队列先进先出的性质来写 　　6、若素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，不可能得到的出栈序列是 dbcaef 根据栈的先进后出的性质写 　　7、假设以数组A[m]存放循环队列的素,其头尾指针分别为front 和rear，则当前队列中的素个数为 (rear-front+m)%m 　　8、在循环队列中，若front与rear分别表示队头素和队尾素的位置，则判断队列空的条件是 front=rear 　　9、从一个顺序循环队列中删除素时，首先需要 后移队首指针 　　10、循环队列存储在数组A[0..m]中，则入队时队尾的操作为rear=(rear+1)%(m+1)其实是 (rear=rear+1)%MaxSise, 此时的MaxSize等于m+1 　　11、允许对队列进行的操作 有删除队头素 　　12、己知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向队头素和队尾索。若初始时队列为空，且要求第1个进入队列的素存储在A[0]处，则初始时front和rear的值分别是 0,n-1 　　13、串的两种最基本的存储方式是 顺序存储 、 链式存储 ，两个串相等的充分必要条件是 两个串的长度相等且字母相同 　　14、串的表示方式：char s[] 或者 char *s 　　15、 下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f(“abba”)返回1，f(“abab”)返回0； 　　16、描述某循环队列的数组为QUEUE[0..M-1]，当循环队列满时，队列中有 M-1 个素 　　17、设循环队列用数组A[1..M]表示，队首、队尾指针分别是FRONT和TAIL，判定队满的条件为 (TAIL+1)%M=FRONT 　　18、20人从1到20编号围成一圈，从1开始报数，报到2的人出列，剩余的人继续从出列人的下一个人报数，则最后剩下的人的编号为 9 　　19、若串S=’software’其子串的个数是 37 字串包括空串1+2+3+4+5+6+7+8=36 36+1=37 1是空串 　　三、数组和广义表 　　1、将8阶三对角矩阵中的所有非零素按照行序为主序方式依次存放于一维数组中，一维数组中的第15个数组素是矩阵的 【正确答案: D】的那个素。 　　A．第5行第3列 B. 第5行第6列 　　C. 第6行第6列 D. 第6行第5列 　　题解：三对角矩阵 　　

　　四、树和二叉树 　　1、二叉排序树，左子树比根节点小，右子树比根节点大 　　2、对一棵二叉树进行中序遍历，可以得到该二叉树所有的结点值按从小到大排列的序列。 　　3、在一棵AVL树（平衡二叉树）中，每个节点的平衡因子的取值范围是 -1~1 　　4、将树转换成二叉树： 　　加线：在兄弟之间加一连线 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 旋转：以树的根结点为轴心，将整树顺时针转45° 　　左边：孩子节点 　　右边：兄弟节点 　　5、森林转换成二叉树 　　将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构 　　6、对于一棵具有n个结点的完全二叉树，若一个结点的编号为i(1≤i≤n)，则它的双亲结点的编号[i/2]，左孩子结点的编号为2i，右孩子结点的编号为2*i+1。 　　7、折半查找的判定树是一个二叉排序树，二叉排序树满足若左子树不空，左子树上的所有结点的值均小于或等于她们的根节点的值，若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值。 　　8、满二叉树：在一棵二叉树中：高度为h的二叉树恰好有2* *h-1 个结点 　　9、二叉树的性质在二叉树的第i层上至多有 2* *(i-1)个结点深度为k的二叉树至多有 2* *k – 1 个结点(k>=1)一棵树高为K的完全二叉树至少有2^(k-1) -1个结点对任何一棵二叉树T，如果其终端结点数(叶子节点数，即度为0的节点数)为n0，度为2的结点数为n2，则 n0=n2+1具有n个结点的完全二叉树的深度为 log2(n) +1如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点 i (1<=i<=n)，有如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是 [ i/2]如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i如果2i+1>n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1若i为奇数且不为1，则结点i的左兄弟是i-1；否则无左兄弟若i为偶数且小于n，则结点i的右兄弟是i+1；否则无右兄弟 　　10、线索二叉树对于具有n个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有2n个指针域。 其中只有n-1个结点被有效指针所指向，即有n-1个非空指针域。 所以共有2n-(n-1) = n+1个空链域n 个结点的线索二叉树上含有的线索数为 n+1(联系上一行) 　　11、从这里开始是作业三 　　在二叉排序树中进行查找的效率与二叉排序树的深度有关 　　12、若二叉树的前序序列与后序序列的次序正好相反，则该二叉树一定是其分支结点的度都为1的二叉树 　　13、对一个满二叉树，m个树枝，n个结点，深度为h，则n = 2* *h-1 　　14、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是 82 　　15、将森林F转换为对应的二叉树T，F中叶结点的个数等于 T中左孩子指针为空的结点个数 　　16、若一棵完全二叉树有767个结点,则叶结点的个数为 384 　　n0：度为0的结点数，n1:度为1的结点 n2：度为2的结点数 　　在二叉树中：n0=n2+1；N=n0+n1+n2 　　n0=(n+1）/2；n0=n2+1；易得n0=(767+1)/2=384. 　　若完全二叉树的节点为n,则其叶子节点个数为: n/2向上取整 　　17、具有12个叶节点的二叉树中有 11 个度为2的节点n0 = n2 +1 　　18、已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是 111 　　18、任何一个无向连通图的最小生成树 一棵或多棵 　　19、图的深度优先遍历类似于二叉树的 先序遍历 　　20、若一颗二叉树的前序遍历序列为a,b,f,e,c,d，中续遍历序列为f,b,a,c,d,e，则该二叉树的后续序列是 f,b,d,c,e,a 　　

　　21、已知n个结点的二叉树具有最小路径长度时，其深度为k，那么第k层上的结点数为 n – 2* *（k-1） + 1前 k-1 层总共有 2* *(k-1)-1个结点所以第 k 层 是 n-[2(n-1)-1] 个结点 　　22、一棵二叉树高度为h，所有结点的度或为0，或为2，则这棵二叉树最少有 2*h-1 　　23、一棵具有 n 个结点的完全二叉树的树高度（深度）是 [logn]+1 ([]表示向下取整) 　　24、对一棵二叉排序树进行 中序 遍历，可以得到该二叉树的所有结点按值从小到大排列的序列。联系二叉排序树的性质 　　25、在二叉树结点的前序序列、中序序列和后序序列中，所有叶子结点的先后顺序 完全相同 　　26、在一棵AVL树(平衡二叉树)中，每个结点的平衡因子的取值范围是 -1 ～ 1 　　27、下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是 【 正确答案: C】。 　　A . B. C.

　　28、由3个结点可以构造出 5 种不同的有向树 　　29、对n(n大于等于2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中： 　　A．该树一定是一棵完全二叉树 ❌完全二叉树意为前n-1层为满二叉树，最后一层连续缺失右边结点的二叉树，而哈夫曼树无法保证最后一层连续缺失右边结点以及前n-1层为满二叉树。所以A错误 　　B．树中一定没有度为1的结点 ✔ 　　C．树中两个权值最小的结点一定是兄弟结点 ✔ 　　D．树中任一非叶结点的权值一定不小于下一层任一结点的权值 ✔ 　　30、若一个具有N个顶点，K条边的无向图是一个森林（N>K），则该森林中必有 N-K 　　31、度为k的树中，第i层最多有 k^(i-1) 个结点 　　32、在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是 [log2 i] = [log2 j] []表示向下取整 　　33、若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有 2 2n 个指针域，其中 n-1 个指针域用于链接孩子结点， n+1 个指针域空闲存放着NULL。 　　34、采用逐点插入法建立序列（54,28,16,34,73,62,95,60,26,43）的二叉排序树后，查找数据素62共进行 3 次素间的比较 　　五、图 　　1、生成树：所有顶点均由边连接在一起，但不存在回路的图一个图可以有许多棵不同的生成树生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图，去掉一条边则非连通一个由n个顶点的连通图的生成树由 n-1 条边在生成树中再加一条必然形成回路含 n 个顶点，n-1 条边的图不一定是生成树。 　　2、最小生成树看主观题 　　已知某带权连通无向图采用邻接矩阵存储方法，邻接矩阵以三组表形式给出，不包括主对角线素在内的下三角形部分素对应的各三组分别为(2,1,16)，(3,1,20)，(3,2,11)，(4,1,19)，(4,3,22)，(5,2,6)，(5,3,14)，(5,4,18)，(6,2,5)，(6,5,9)，(5,1,∞)，(6,1,∞)，(4,2,∞)，(6,3,∞)，(6,4,∞)。该连通图的最小生成树的权值是 56 　　3、最短路径：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径 　　注：最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边第一类问题：两点间最短路径（单源最短路径）（Dijkstra算法）第二类问题：某源点到其他个点最短路径（所有顶点间的最短路径）（Floyed算法） 　　Dijkstra算法： 　　初始时令S={vo}，T={其余顶点}。 　　T中顶点对应的距离值用辅助数组D存放。 　　D[j] 初值:若<Vo,vi>存在，则为其权值;否则为oo。 　　从T中选取一个其距离值最小的顶点 vj，加入S,D[j]= Min{D[i]lv, eT} 　　对T中顶点的距离值进行修改:若加进 Vi 作中间顶点，从V0到vi的距离值比不加Vj 的路径要短，则修改此距离值。 　　



　　题目： 　　1、有向带权图，若采用迪杰斯特拉（Dijkstra）算法求源点a到其他各顶点的最短路径，得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是 f,d,e 　　

　　解析：

　　4 　　2、用迪杰斯特拉算法计算下图中A到G的最短路径为 ABEG 【 正确答案: ABEG】 　　

　　解题思路： 　　

　　Floyed算法 　　算法思想：逐个顶点试探从Vi 到 V j的所有可能存在的路径选出一条长度最短的路径 　　AOV网定义——拓扑排序 　　在一个有向图中，若用顶点表示活动，有向边表示活动间先后关系，称该有向图叫做顶点表示活动的网(Activity On Vertex network)简称为AOV网 　　AOV网：有向无环图 　　拓扑排序：在AOV 网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若AOV网中有弧<i, j>存在，则在这个序列中，i一定排在j的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。 　　检测AOV 网中是否存在环方法:对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。 　　AOE网定义——-关键路径 　　若在带权的有向图中,以顶点表示事件,有向边表示活动，边上的权值表示完成该活动的开销（如该活动所需的时间），则称此带权的有向图为用边表示活动的网络，简称AOE网 　　4、设无向图的顶点个数为n，则该图最多有 n(n-1)/2 条边 　　一个n个顶点的连通无向图，其边的个数至少为 n-1 　　5、在一个无向图中，所有顶点的度数之和等于所有边数 2 倍，在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 1 倍。 　　6、在有向图的邻接表存储结构中，顶点V在链表结点中出现的次数是 顶点v的入度。 　　例： 　　

　　6.1 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的 度 【 正确答案: 度数 或 度】 ；对于有向图来说等于该顶点的 出度 【 正确答案: 出度】 。 　　无向图的邻接表： 　　

　　有向图的邻接表： 　　

　　7、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是 　　A G中有弧<Vi，Vj> B G中有一条从Vi到Vj的路径 　　C G中没有弧<Vi,Vj> D G中有一条从Vj到Vi的路径 　　8、在用邻接表表示图时，拓扑排序算法时间复杂度为 O(n＋e) 　　9、利用拓扑排序方法判断有向图存在回路的条件是不存在入度为 0的节点。 　　10、若无向图G=(V，E)中含15个顶点，若保证图G是连通的，则需要的边数最少是 14 　　11、任何一个无向连通图的最小生成树 一棵或多棵。 　　12、对含有n条边的无向图而言，其邻接表中边数为 2n 　　13、用邻接表表示图进行广度优先遍历时，通常是采用 队列 来实现算法的。 　　14、一个n个顶点的连通无向图，其边的个数至少为 n-1 　　15、n个节点的完全有向图含有边的数目 n(n-1) 　　16、若具有n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵一定为一个 对称矩阵 　　六、排序 　　

　　填空题 　　1、比较次数达到树形选择排序水平，同时又不增加存储用以保存树形选择排序中比较的中间结果的排序方法是 堆排序 　　2、对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为 25 的值除以9。 　　折半查找的时间复杂度为 log2(n)x/9=log2^9第五个查找1次 第二个和第七个查找两次 第一，第三和第六，第八要查找三次 第四和第九要查找四次 一共25次 根据二叉判定树的方法确定查找次数

　　3、对N 个素的表做顺序查找时，若查找每个素的概率相同，则平均查找长度为 （N+1）/2 　　4、当采用分块查找时，数据的组织方式为 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 　　5、在具有n个素的序列中进行查找，平均查找长度为O(n)的方法是 顺序查找方法 　　6、在二叉排序树中进行查找的效率与 二叉排序树的深度有关 　　7、下列选项中，不能构成折半查找中关键字比较序列的是 A 　　A 500，200，450，180 　　B 500，450，200，180 　　C 180，500，200，450 　　D 180，200，500，450 　　解析：因为折半查找的判定树是一棵二叉排序树，看其是否满足二叉排序树的要求。 　　

　　8、假设排序过程中序列的变化情况如下，可以断定，所采用的排序方法是 D方法 　　初始状态: 50，72，28，39，81，15 　　第1趟: 15，72，28，39，50，81 　　第2趟: 15，50，28，39，72，81 　　第3趟: 15，39，28，50，72，81 　　第4趟: 28，15，39，50，72，81 　　第5趟: 15，28，39，50，72，81 　　A.插入排序 B.泡排序 　　C.选择排序 D.堆排序 　　解析：

　　9、快速排序在平均情况下的时间复杂度为 O(nlogn)，在最环情况下的时间复杂度为 O(n^2) 　　10、某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，素序列的若干中间状态（按先后出现次序排列，但不一定是连续的）如下： （1） 25，84，21，47，15，27，68，35，20 （2） 20，15，21，25，47，27，68，35，84 （3） 15，20，21，25，35，27，47，68，84 （4） 15，20，21，25，27，35，47，68，84 则所采用的排序方法是： 【 正确答案: D】 　　A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序 　　解析：A肯定不对， 　　希尔排序：

　　11、给出一组关键字序列{12,2,16,30,8,28,4,10,20,6,18}，当用希尔排序（第一趟增量为5）从小到大进行排序第一趟结束时的序列为 12，2，10，20，6，18，4，16，30，8，28 　　解析： 　　

　　12、给出一组关键字序列{12,2,16,30,8,28,4,10,20,6,18}，当用链式基数排序（基数为10）从小到大进行排序第一趟结束时的序列为 30，10，20，12，2，4，16，6，8，28，18 　　13、对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15},则采用的是希尔排序 　　14、采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是 递归次数与每次划分后得到的分区的处理顺序无关。 　　15、已知关键字序列5,8,12,19,28,20,15,22是小根堆（最小堆），插入关键字3，则调整后得到的小根堆是 3,5,12,8,28,20,15,22,19 　　解析： 　　

　　16、为实现快速排序算法，待排序序列宜采用的存储方式是 顺序存储 　　17、给出一组关键字序列{12,2,16,30,8,28,4,10,20,6,18}，当用快速排序（选第一个记录为基准点进行划分）从小到大进行排序第一趟结束时的序列为 【 正确答案: C】 　　A. 6，2，8，10，4，12，28，30，16，20，18 　　B. 6，4，8，10，2，12，28，30，16，20，18 　　C. 4，2，6，10，8，12，28，30，20，16，18 　　D. 4，2，8，10，6，12，16，20，28，30，18 　　解析： 　　直接交换法： 　　

　　18、已知一个长度为16的顺序表L，其素按关键字有序排列。若采用折半查找法查找一个L中不存在的素，则关键字比较次数最多为 5 次 　　

　　解析：若果问比较次数，画出二叉判定树 　　

　　19、在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需要比较 3 次 　　解析：插入60前的序列为：15 ，23，38，54，72，96，60，45，83，如果将60插入到前面的有序区，60需要和96，72，54比较，总共需要比较三次。 　　20、对序列(49,38,65,97,76,13,47,50)采用折半插入排序法进行排序，若把第7个素47插入到已排序序列中，为寻找插入的合适位置需要进行 3 次素间的比较。 　　21、在有序表(k1,k2,…,k99)中采用折半查找方法查找99次，其中至少有一个素被比较了99次，该素是 k50 　　22、采用逐点插入法建立序列（54,28,16,34,73,62,95,60,26,43）的二叉排序树后，查找数据素62共进行 3 次素间的比较 　　解析：

　　23、折半查找过程可以利用一棵称之为”判定树”的二叉树来描述。在长度为12的序列中进行折半查找对应判定树的根结点右孩子的值（某素在序列中的位置）是 9 。 　　解析： 　　数列序号为0-11

　　6.1 插入排序： 　　直接插入排序、折半插入排序、希尔排序 　　插入排序：基本思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。即便插入边排序，保证子序列中随时都是排好序的。基本操作：有序插入在插入a[i]前，数组a的前半段(a[0]~a[i-1])是有序段，后半段(a[li]~a[n-1])是停留于输入次序的“无序段”。插入a[li]使a[0]~a[i-1]有序，也就是要为a[i]找到有序位置j (O≤j<=i)将a[i]插入在a[j]的位置上。 　　直接插入排序： 　　思想：将待排序列划分为有序区与无序区。默认第一个素有序，依次遍历之后每一个素，将素 a[i] 按大小顺序插入到 0 ~ i 的位置。一直重复插入，直到第n个素。（找素，寻位置，插素） 　　动图演示： 　　

　　代码展示： 　　折半插入排序： 　　思想：顺序地把待排序的序列中的各个素按其关键字的大小，通过折半查找插入到已排序的序列的适当位置。 　　实现：①将待排序序列的第一个素看做一个有序序列，把第二个素到最后一个素当成是未排序序列；②依次遍历后续素，将扫描到的每个素插入有序序列的适当位置，在查找素的适当位置时，采用了折半查找方法。（如果待插入的素与有序序列中的某个素相等，则将待插入素插入到相等素的后面。） 　　代码展示： 　　希尔排序： 　　基本思想：先将整个待排记录序列分割成若子序列，分别进行直接插入排序（分组插入），使整个数组逐渐变成部分有序数组，然后逐渐减少分组，最后合并分组即组数为1。 　　较于插入排序的优化原理：普通插入排序对少量数据效率高；普通插入排序对越有序的数据效率越高； 　　实现： 　　①选择一个间隔step，即每次将数组长度对半取，分组; 　　②对每一个分组排序; 　　③重复上述过程，直到step = 1; 　　例子:

　　代码展示： 　　6.2 交换排序： 　　基本思想：两两比较，如果发生逆序则交换，直到所有记录都排好为止。 　　冒泡排序O(n2)： 　　思想：是一种基于比较的算法，从第一个素开始，每次比较相邻素。默认为升序排列，所以一旦遇到顺序不正确的素就两两交换位置，并进行下一次比较。 　　n个记录，总共需要n-1趟 　　第 m 趟需要比较 n-m 次 　　动态演示： 　　

　　代码演示： 　　排序过程： 　　第一趟排序结果：[7,5,3,1,9]，第二趟：[5,3,1,7,9] 　　最坏情况下比较次数：n(n-1)/2 　　平均时间复杂度：O（n²） 　　Tips： 　　每一趟排序都能将无序区最大的数加入到有序区，所以在算法实现部分需注意第二个for循环的终止条件！ 　　快速排序（O(nlog2n)： 　　思想：是一种较冒泡排序更优的排序算法（不稳定），它采用分而治之的思想。每次排序都会选择一个数作为基数，然后以这个数为基准，小于该值的数交换到左边，大于该值的数交换到右边，重复操作，直到整个序列有序。 　　遍历，j先遍历（因为基数是最左边的数）,即j–，直到找到小于基数的数停下来；然后i遍历，i++，直到找到一个数大于基数的数停下来；交换i和j所对应的值。 　　重复上述遍历交换过程，直到i与j相遇，交换基数与i对应素的位置，此时第一次排序结束。 　　实例演示：以一个数组作为示例，取区间第一个数为基准数。0 　　初始时，i = 0; j = 9; X = a[i] = 72由于已经将 a[0] 中的数保存到 X 中，可以理解成在数组 a[0] 上挖了个坑，可以将其它数据填充到这来。从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j–;数组变为：0 　　i = 3; j = 7; X=72再重复上面的步骤，先从后向前找，再从前向后找。从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;从i开始向后找，当i=5时，由于i==j退出。此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。数组变为：0 　　可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。 对挖坑填数进行总结:1 i =L; j = R; 将基准数挖出形成第一个坑a[i]。2 j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。3 i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。 　　代码展示： 　　6.3选择排序： 　　简单选择排序： 　　思想：选择数组最小的素，与数组第一个素交换，然后选择剩余的数组素中最小的素，与数组第二个素交换，一直重复上述操作，直到数组有序。 　　动图演示： 　　

　　代码展示： 　　时间复杂度：O(n^2) 　　堆排序： 　　思想： 　　堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列； 　　算法步骤：将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；将堆顶素R[1]与最后一个素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的素个数为n-1，则整个排序过程完成。 　　动图演示： 　　

　　6.4归并排序O(nlog2(n))： 　　基本思想： 　　归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 　　算法描述：把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。 　　动图演示： 　　

　　演示：





　　6.5 基数排序 　　基本思想： 　　基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数； 　　基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。 　　算法描述：取得数组中的最大数，并取得位数；arr为原始数组，从最低位开始取每个位组成radix数组；对radix进行计数排序（利用计数排序适用于小范围数的特点）； 　　动图演示： 　　

　　七、查找 　　折半查找 　　

　　

　　【例8.3】给定共有11个数据素的有序表（2,3,10,15,20,25,28,29,30,35,40），采用折半查找，试问： 　　（1）若查找给定值为20的素，将依次与表中哪些素比较？ （2）若查找给定值为26的素，将依次与哪些素比较？ （3）假设查找表中每个素的概率相同，求查找成功时的平均查找长度和查找不成功时的平均查找长度。。 　　画出判定树： 　　

　　（1）25，10，15，20 　　（2）25，30，28 　　（3）

　　从上例看到，成功的折半查找过程恰好是走了一条从判定树的根到被查记录的路径，经历比较的关键字次数恰为该记录在树中的层数。 　　若查找失败，则其比较过程是经历了一条从判定树根到某个外部结点的路径，所需的关键字比较次数是该路径上内部结点的总数。 　　二叉排序树 　　二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树： （1）若它的左子树非空，则左子树上所有记录的值均小于根记录的值； （2）若它的右子树非空,则右子树上所有记录的值均大于根记录的值； （3）左、右子树本身又各是一棵二叉排序树。 　　注意：二叉排序树中没有相同关键字的结点。 　　平衡二叉树 　　若一棵二叉树中每个结点的左、右子树的高度至多相差1,则称此二叉树为平衡二叉树。 在算法中，通过平衡因子（balancd factor，用bf表示）来具体实现上述平衡二叉树的定义。 平衡因子：平衡二叉树中每个结点有一个平衡因子域，每个结点的平衡因子是该结点左子树的高度减去右子树的高度。从平衡因子的角度可以说，若一棵二叉树中所有结点的平衡因子的绝对值小于或等于1，即平衡因子取值为1、0或-1，则该二叉树称为平衡二叉树。 　　平衡因子：该节点的左子树的高度 – 右子树的高度 　　（1）LL型调整（左子树的左子树） 　　

　　（2）RR型调整（右子树的右子树） 　　

　　（3）LR型调整（左子树的右子树） 　　

　　（4）RL型（右子树的左子树） 　　

　　例子：输入关键字序列{16,3,7,11,9,26,18,14,15},给出构造一棵AVL（平衡二叉树）树的步骤。