c 网站开发教程,南昌模板建站定制,wordpress暂停网站,鲜花网站建设策划方案书自己在学习过程中总结了DS中几乎所有的应用题#xff0c;可以用于速通期末考/考研/各种考试。很多方法来源于B站大佬#xff0c;底层原理本文不做过多介绍#xff0c;建议自己研究。例题大部分选自紫皮严书。pdf版在主页资源 一、递归时间/空间分析
1.时间复杂度的分析
设… 自己在学习过程中总结了DS中几乎所有的应用题可以用于速通期末考/考研/各种考试。很多方法来源于B站大佬底层原理本文不做过多介绍建议自己研究。例题大部分选自紫皮严书。pdf版在主页资源 一、递归时间/空间分析
1.时间复杂度的分析
设 F a c t ( n ) Fact(n) Fact(n)的执行时间是 T ( n ) T(n) T(n)。 if(n0) return 1; 的执行时间是 O ( 1 ) O(1) O(1), F a c t ( n − 1 ) Fact(n-1) Fact(n−1)的执行时间是 T ( n − 1 ) T(n-1) T(n−1), 所以else return n ∗ F a c t ( n − 1 ) n*Fact(n-1) n∗Fact(n−1); 的执行时间是 O ( 1 ) T ( n − 1 ) O(1)T(n-1) O(1)T(n−1)。
推出 T ( n ) n C T ( 0 ) n C D T(n)nCT(0)nCD T(n)nCT(0)nCD T ( n ) O ( n ) T(n)O(n) T(n)O(n)
【小结论】Fibonacci数列和Hanoi塔问题递归算法的时间复杂度均为O(2^n)。2.空间复杂度分析
空间复杂度 S ( n ) O ( f ( n ) ) S(n)O(f(n)) S(n)O(f(n))其中 f ( n ) f(n) f(n)为“递归工作栈”中工作记录的个数与问题规模 n n n 的函数关系。
【小结论】阶乘间题、Fibonacci数列问题、Hanoi塔问题的递归算法的空间复杂度均为O(n)。二、KMP算法求next数组和nextval
1.next[i]
前2位一般为0,1 i位看前i-1位最大公共部分末尾坐标1
2.nexval[i]
前1位一般为0 t[next[i]]位置元素是不是和t[i]一样一样的话将t[next[i]]的nextval写在当前nextval[i]不一样的话就将当前的next[i]里面数写在nextval[i] 例题1已知模式串t“abcaabbabcab”, 写出用KMP法求得的每个字符对应的next和nextval函数值。 例题2、3 三、数组存贮选择简答
1.对称矩阵 2.三角矩阵
(1)上三角
(2)下三角 例题1假设以行序为主序存储二维数组 A array[ 1…100, 1…100] , 设每个数据元素占2个存储单元基地址为10, 则 LOC[5,5] ( )。 【解析】LOC[5,5]有(5-1)满行最后一行有(5-1)个 Loc[5,5](4*1004)*210818 例题2数组A中每个元素A[i,j]的长度均为32个二进制位行下标从-1~9, 列下标从1 ~11,从首地址S开始连续存放在主存储器中主存储器字长为16位。 求 1存放该数组所需多少单元 32/162字 11 * 11 * 2242 2存放数组第4列所有元素至少需多少单元 11*222 3数组按行存放时元素A[7,4]的起始地址是多少 【解析】A[7,4]有(7-12)满行最后一行有(4)个 S((62)*114-1)*2S182 4数组按列存放时元素 A[4, 7]的起始地址是多少 【解析】A[4, 7]有6满列最后一列有(42)个 S((7-1)*11(42)-1)*2S142 例题3设有一个 10 阶的对称矩阵 A , 采用压缩存储方式以行序为主存储a11为第一元素 其存储地址为1,每个元素占一个地址空间则a85的地址为( )。 (易错)若对n阶对称矩阵A以行序为主序方式将其下三角形的元素包括主对角线上所有元素依次存放于一维数组 B[1…(n (n1))/2]中则在B中确定aij (ij)的位置k的关系为 本来是i (i -1)/2 j但是(ij) 所以j(j-1)/2i 四、广义表—求表头/表尾/长度/深度选择简答
1.取表头Head(A)
就取A的第一个元素
2.取表尾Tail(A)
就是扣掉第一个元素留下的所有的包含A最外面的大括号
3.长度
就是元素的个数 //严书例子 (1) A ()—A 是一个空表 其长度为零。 (2) B(e)—B 只有一个原子 e, 其长度为1。 (3) C (a, (b, c, d))—C的长度为2, 两个元素分别为原子 a 和子表(b,c, d)。 (4) D (A, B, C)—D 的长度为3,3个元素都是广义表。显然将子表的值代入后则有 D ((), (e), (a, (b, c, d)))。 (5) E (a, E)—这是一个递归的表其长度为2。E 相当千一个无限的广义表 E(a, (a, (a, ···)))。 4.深度
就是数左or右括号的个数 例题1设广义表 L ((a,b,c)), 则 L 的长度和深度分别为( ) 长度就是元素个数1 深度就是数括号个数2 例题2广义表((a,b,c,d))的表头是( ),表尾是( ) 取表头Head(A)就取A的第一个元素(a,b,c,d) 取表尾Tail(A)就是扣掉第一个元素留下的所有的包含A最外面的大括号( ) 例题3广义表 A (a,b,(c,d),(e,(f,g))), 则 Head(Tail(Head(Tail(Tail(A)))))的值为( )。 Tail(A) (b,(c,d),(e,(f,g))) Tail(Tail(A)) ( (c,d),(e,(f,g))) Head(Tail(Tail(A))) (c,d) Tail(Head(Tail(Tail(A)))) (d) Head(Tail(Head(Tail(Tail(A)))))d 例题4请将香蕉 banana 用工具H( )—Head( ), T()—Tail( )从L中取出。 L (apple, (orange, (strawberry, (banana)), peach), pear) 五、前/中/后/层序遍历二叉树先后根遍历森林
1.前序/前缀表达式/波兰式
树根左右 森林根左到右 RADEBCFGHK
2.中序/中缀表示
树左根右 把一个树拍扁了就是中序~
3.后序/后缀表达式/逆波兰式
树左右根 森林左到右根 DEABGHKFCR 例题1试找出满足下列条件的二叉树 ①先序序列与后序序列相同 【解析】根左右 左右 根不能删根 空树只有根。 ②中序序列与后序序列相同。 【解析】左根右 左右 根根左右不能删根 空树只有左子树 ③先序序列与中序序列相同。 【解析】根左 右左 根右不能删根 空树只有右子树 ④中序序列与层次遍历序列相同。 【解析】左 根右层序先输出根不能删根 空树只有右子树 六、前/后/层次中序确定二叉树
1.前序中序 例题1设一棵二叉树的先序序列ABDFCEGH中序序列BFDAGEHC。 ①画出这棵二叉树。 ②画出这棵二叉树的后序线索树。后面 ③将这棵二叉树转换成对应的树或森林。后面 2.后序中序 例题2已知后序序列DABEC中序序列DEBAC求二叉树 3.层次中序 例题3已知层序序列ABCDEF中序序列BADCFE求二叉树 4.拓展
①已知前序有多少种二叉树? 入栈出栈个数 1 / ( n 1 ) C 2 n n 1/(n1) C_2n^n 1/(n1)C2nn种n为结点个数
七、前中后序线索二叉树的构建
1.线索二叉树构建方法
Step1写出对应的先/中/后序遍历 Step2如果结点左孩子为空结点左链连接序列左边的元素如果结点右孩子为空结点右链连接序列右边的元素 例题1设一棵二叉树的先序序列ABDFCEGH中序序列BFDAGEHC。 ①画出这棵二叉树。 ②画出这棵二叉树的后序线索树。 ③将这棵二叉树转换成对应的树或森林。后面 八、树/森林与二叉树的转换
变森林/树删右腿 变二叉树连右兄弟
1.树→二叉树 2. 二叉树→树 3.森林转→二叉树 4.二叉树→森林 例题1设一棵二叉树的先序序列ABDFCEGH中序序列BFDAGEHC。 ①画出这棵二叉树。 ②画出这棵二叉树的后序线索树。 ③将这棵二叉树转换成对应的树或森林。 九、哈夫曼树——构造/WPL/HT初始和终结状态 例题1已知w (5,29,7,8,14,23,3,11), 构造一棵哈夫曼树计算树的带权路径长度并给出其构造过程中存储结构HT的初始状态和终结状态。 ①哈夫曼树 或 ②WPL29211374553583143232 271 ③ 例题2假设用于通信的电文仅由8个字母组成字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21 , 0.10。 ①试为这8个字母设计哈夫曼编码。 ②试设计另一种由二进制表示的等长编码方案。 等长编码需要3位2进制 ③对于上述实例比较两种方案的优缺点。 哈夫曼WPL2*(0.190.210.32)4*(0.070.100.06)5*(0.020.03)2.61平均码长 等长WPL3*(0.190.320.210.070.060.100.020.03)3平均码长 十、邻接矩阵/邻接表/逆邻接表/十字链表—构建、出入度
1.邻接矩阵
①无向图
出入度第i行or第j列非零元素的个数是顶点i的度
②有向图
出入度第i行非零元素的个数是顶点i的出度第j列非零元素的个数正好是顶点i的入度
2.邻接表
①无向图
info是权重
出入度遍历“一行”
②有向图
出度遍历“一行” 入度遍历v的每行
3.逆邻接表
与邻接表箭头相反
4.十字链表 十字链表的画法 Step1.编号 Step2.组队编号结点出去的箭头 Step3.连线前同横线后同竖线 例题1已知有向图请给出 ①每个顶点的入度和出度 1的出0入3 2的出2入2 3的出2入1 4的出3入1 5的出1入2 6的出3入2 ②邻接矩阵 1 2 3 4 5 6 1 0 0 0 0 0 0 2 1 0 0 1 0 0 3 0 1 0 0 0 1 4 0 0 1 0 1 1 5 1 0 0 0 0 0 6 1 1 0 0 1 0 ③邻接表 ④逆邻接表。 例题2已知无向网请给出 ①邻接矩阵 ②邻接表 ③最小生成树。后面 十一、生成树—深度优先/广度优先 已知图的邻接矩阵。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。 深度优先 广度优先 十二、最小生成树—Prim/Kruskal
1.普里姆 (Prim) 算法
从某点出发找最短的边加入集合再以集合为整体继续加入边。过程中不能出现回路 例题1 1→6→5→2→3→4不唯一 2.克鲁斯卡尔 (Kruskal) 算法
直接找最小的边过程中不能出现回路 例题1 例题2 已知无向网请给出 ②邻接表 ③最小生成树。 ③Kruskal 十三、最短路径—Dijkstra/Floyd
1.从某个源点到其余各顶点的最短路径迪杰斯特拉Dijkstra算法
从某点出发找最短的边加入集合再以集合为整体继续加入边。 与Prim不同的是Prim只用看集合相连的最短Dijkstra还要算一算。 例题1试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径 2.每一对顶点之间的最短路径弗洛伊德(Floyd)算法
不断基于对角线上元素画“十字”计算的过程 Step1.从第一个对角线元素开始不断画十字 Step2.十字和它∞部分对应的行列值不变 Step3.更新值值比原来元素小才更新与路径取下一个对角线元素继续重复 对于更新路径A1中[5,2]从∞(5_31→2_12)更新为7(5→1→2) 十四、拓扑排序/逆拓扑排序
1.AOV-网
这种用顶点表示活动用弧表示活动间的优先关系的有向图称为顶点表示活动的网。AOV-网是无环的有向图(DAG)
2. 拓扑排序
就是将AOV-网中所有顶点排成一个线性序列该序列满足若在AOV-网中由顶点Vi到顶点Vj有一条路径,则在该线性序列中的顶点Vi必定在顶点Vj之前。
拓扑排序做法 Step1.在有向图中选一个无前驱的顶点且输出它。 Step2.从图中删除该顶点和所有以它为尾的弧。 Step3.重复1.和2.直至不存在无前驱的顶点。 若此时输出的顶点数小于有向图中的顶点数则说明有向图中存在环否则输出的顶点序列即为一个拓扑序列。
逆拓扑排序做法 在有向图中选一个无后继的顶点且输出它。其余和拓扑排序一样 例题1 十五、AOE-网—事件活动最早/最迟/时间余量/关键活动/关键路径
1. AOE-网
AOE-网是一个带权的有向无环图其中顶点表示事件弧表示活动权表示活动持续的时间
ve(1):事件v_1的最早发生时间 vl(1):事件v_1的最迟发生时间
早顺迟逆早迟-早大迟小 说明最早时间从源点顺着往汇点走 最迟时间从汇点逆着往源点走 最早时间顺着走的时候遇到两条道路选相加最大的 最迟时间逆着走的时候遇到两条道路选相减最小的
e(1):活动a_1的最早开始时间 l(1): 活动a_1的最迟开始时间 早弧尾早迟弧头迟-权值 说明最早时间是x,y弧尾事件的最早开始时间 最迟时间是x,y弧头事件的最迟开始时间-x,y的权值
2.关键路径
关键路径上的活动没有时间余量即l(1)-e(1)0 关键路径路径长度最长的路径完成工程至少需要的时间 关键路径上的活动是影响工程的关键活动 例题1 ①求这个工程最早可能在什么时间结束 ve(i) vl(i) 1 0 2 19 3 15 4 29 5 38 6 43 ve(i) vl(i) 1 0 0 2 19 19 3 15 15 4 29 37 5 38 38 6 43 43 最早结束时间:43 ②求每个活动的最早开始时间和最早开始时间 ③确定哪些活动是关键活动。 1,33,22,55,6 ④关键路径 1,3,2,5,6 例题2 acg18 aeh 18 bfh 27 bdcg 27 bdeh 27 关键路径路径长度最长的路径。 答案C 十六、顺序查找—顺序/折半/分块
1.顺序
(1)普通顺序查找 ASL成功 ( ( 1 2 3 ⋯ n ) ) / n ( 1 n ) / 2 ((123⋯n))/n(1n)/2 ((123⋯n))/n(1n)/2 ASL不成功 n 1 n1 n1 时间复杂度: O ( n ) O(n) O(n)
(2)有序表的顺序查找
ASL不成功 ( ( 1 2 3 ⋯ n n ) ) / ( n 1 ) n / 2 n / ( n 1 ) ((123⋯nn))/(n1)n/2n/(n1) ((123⋯nn))/(n1)n/2n/(n1)
2.折半
要求线性表必须采用顺序存储结构而且表中元素按关键字有序排列
ASL成功
时间复杂度为:$O(log_2 n)$3.分块 ASL成功 LbLw Lb为查找索引表确定所在块的平均查找长度Lw为在块中查找元素的平均查找长度 例题1 假定对有序表(3, 4, 5, 7, 24, 30, 42, 54, 63, 72, 87, 95) 进行折半查找试回答下列问题。编号从1开始 ①画出描述折半查找过程的判定树。 ②若查找元素54, 需依次与哪些元素比较 30,63,42,54 ③若查找元素90, 需依次与哪些元素比较 30,63,87,95 ④假定每个元素的查找概率相等求查找成功时的平均查找长度。 ASL成功(11223445)/1237/12 十七、树表的查找—BTS/AVL/B/B
1.二叉排序树(BTS)
(1)定义 ①若它的左子树不空则左子树上所有结点的值均小于它的根结点的值 ②若它的右子树不空则右子树上所有结点的值均大于它的根结点的值 ③它的左、右子树也分别为二叉排序树。
(2)性质 中序遍历一棵二叉树时可以得到一个结点值递增的有序序列
(3)插入 插入一定是叶子结点
(4)构造
(5)删除 ①删叶子直接删 ②删无左孩子/无右孩子孩子替换要删的结点 ③删有左右孩子找中序遍历的直接前驱/后继替换要删的结点删去这个前驱/后继变为①② 【说明】反正保证二叉排序树中序遍历有序就行 (6)ASL O()
ASLa成功(11223443)/102.9 ASLa不成功(3546)/113.545
若二叉排序树左右子树高度只差的绝对值不超过1(平衡二叉树),它的平均查找长度为O(log2n)。 若二叉排序树是一个只有右左孩子的单支树类似于有序的单链表)则其平均查找长度为O(n)。
2.平衡二叉树AVL
(1)定义 结点左子树与右子树的高度差为该结点的平衡因子则平衡二叉树结点的平衡因子的值只可能是-1、0或1。
(2)插入 从接入的点往上找“最小不平衡子树”的根找根在这条路径上最近的3个结点调整调整完剩余结点按定义去放 ①LR
②LL
③RR
④RL
(3)O() 时间复杂度O(log2n)
3.B-树
(1)定义 一棵m阶的B树或为空树是所有结点的平衡因子0的m路平衡查找树
①树中每个结点至多有m棵子树最多有m-1个关键字 ②若根结点不是叶子结点则至少有两棵子树 ③除根之外的所有非终端结点至少有 个子树至少含有 个关键字 ④所有的叶子结点都出现在同一层次上并且不带信息通常称为失败结点失败结点并不存在指向这些结点的指针为空。引入失败结点是为了便于分析B-树的查找性能
4.B树 B树和B-树的差异 (1)有n棵子树的结点中含有n个关键字 (2)所有的叶子结点中包含了全部关键字的信息以及指向含这些关键字记录的指针且叶 子结点本身依关键字的大小自小而大顺序链接 (3)所有的非终端结点可以看成是索引部分结点中仅含有其子树根结点中的最大或最小关键字。 例题1 在一棵空的二叉排序树中依次插入关键字序列为 12, 7, 17, 11, 16, 2, 13, 9, 21, 4, 请画出所得到的二叉排序树。 说明验算办法用中序遍历应得到排序结果:2,4,7,9,11,12,13,16,17,21 十八、散列表—构造/冲突/查找
①散列函数和散列地址在记录的存储位置p和其关键字key之间建立一个确定的对应关系H, 使pH(key), 称这个对应关系H为散列函数p为散列地址。
1.构造方法
除留余数法假设散列表表长为m, 选择一个不大于m的数p, 用p去除关键字除后所得余数为散列地址即H(key) key%p。一般情况下可以选p为小于表长的最大质数。
2.处理冲突的方法
(1)开放地址法 H i ( H ( k e y ) d i ) H_i (H(key) d_i)%m Hi(H(key)di) ①线性探测法d_i l, 2, 3, …, m-1 ②二次探测法
(2)链地址法
3. 查找
查找过程中需和给定值进行比较的关键字的个数取决于三个因素散列函数、处理冲突 的方法和散列表的装填因子a 列表的装填因子a定义为 a表中填入的记录数/散列表的长度 例题1 对于的关键字(19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79), 设散列函数为 H(key) key %13, 用线性探测法处理冲突。设表长为16, 试构造这组关键字的散列表并计算查找成功和查找失败时的平均查找长度。 H(19)6,H(14)1,H(23)10 H(1)1发生冲突,H(1)(11)%132 H(68)3,H(20)7,H(84)8 H(27)1发生冲突,H(27)(11)%132发生冲突,H(27)(12)%133发生冲突,H(27)(13)%134 H(55)3发生冲突,H(55)(31)%134发生冲突,H(55)(32)%135 H(11)11 H(10)10发生冲突,H(10)(101)%1311发生冲突, H(10)(102)%1312 H(79)1发生冲突,H(79)(11)%132发生冲突, H(79)(12)%133发生冲突, H(79)(13)%134发生冲突, H(79)(15)%135发生冲突,….,直到H(79)(18)%139 散列地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 关键字 14 1 68 27 55 19 20 84 79 23 11 10 比较次数 1 2 1 4 3 1 1 3 9 1 1 3 ASL成功(121431139113)/122.5 比较次数相加/占有散列地址的个数 ASL失败(1131211109876 5432)/13 0查找1次失败 1查找13次失败2查找12次失败 … 对于 注意 1查找失败2次 例题2 已知一组关键字为 (19, 14, 23, 1, 68, 20, 8 4, 27, 55, 11, 10 , 79), 设散列函数 H(key) key %13, 用链地址法处理冲突试构造这组关键字的散列表计算查找成功和查找失败时的平均查找长度。 例题3 设散列表的地址范围为017散列函数为:H(key)key%16。用线性探测法处理冲突,输入关键字序列:(10,24,32,17,31,30,46,47,40,63,49)构造散列表,试回答下列问题: ①画出散列表的示意图。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 关键字 32 17 63 49 24 40 10 30 31 46 47 比较次数 1 1 6 3 1 2 1 1 1 3 3 ②若查找关键字63需要依次与哪些关键字进行比较? 31,46,47,32,17,63 ③若查找关键字60需要依次与哪些关键字进行比较? H(60)12,与空对比 ④假定每个关键字的查找概率相等求查找成功时的平均查找长度。 ASL成功(11631211133)/1123/11 例题4 设有一组关键字 (9, 1, 23, 14, 55, 20, 84, 27), 采用散列函数H(key) key%7, 表长为 10, 用开放地址法的二次探测法处理冲突。要求对该关键字序列构造散列表并计算查找成功的平均查找长度。 H(84)84%70H(84)(01)%71, H(84)(0-1)%76H(84)(04)%74 H(27)27%76H(27)(61)%70, H(27)(6-1)%75 0 1 2 3 4 5 6 7 8 9 关键字 14 1 9 23 84 27 55 20 比较次数 1 1 1 2 4 3 1 2 ASLsucc(11124312)/815/8 例题5 散列函数H(K) 3K % 11 , 散列地址空间为 0~10, 对关键字序列 (32, 13, 49, 24, 38, 21, 4, 12), 按下述两种解决冲突的方法构造散列表并分别求出等概率下查找成功时和查找失败时的平均查找长度 ASLsucc和 ASLunsucc ①线性探测法。 0 1 2 3 4 5 6 7 8 9 10 关键字 4 12 49 38 13 24 32 21 比较次数 1 1 1 2 1 2 1 2 ASLsucc(11121212)/811/8 ASLunsucc(12187654321)/1140/11 ②链地址法。 ASLsucc(1523)/811/8 ASLunsucc(16223*3)/1119/11 十九、插入排序—直接插入/折半插入/希尔
1.直接插入排序
后面没有排好的一个一个往排好的里面丢比较时候根排好的最后一个元素比
2.折半插入排序
后面没有排好的一个一个往排好的里面丢比较时候根排好的中间元素比 但对于数据量不很大的排序表折半插入排序往往能表现出很好的性能。折半插入排序仅减少了比较元素的次数约O(nlogn)元素的移动次数并未改变它依赖于待排序表的初始状态。
3.希尔排序
Step1.定义增量序列Dk : DmDm-1…D11互质 Step2.对每个Dk进行Dk间隔插入排序 例题1 设待排序的关键字序列为{12,2,16,30,28,10,16*,20,6,18}, 试分别写出使用以下排序方法 每趟排序结束后关键字序列的状态。 ①直接插入排序 {12,2,16,30,28,10,16,20,6,18} 第1趟{(2,12,)16,30,28,10,16,20,6,18} 第2趟{(2,12,16,)30,28,10,16,20,6,18} 第3趟{(2,12,16,30,)28,10,16,20,6,18} 第4趟{(2,12,16,28,30,)10,16,20,6,18} 第5趟{(2,10,12,16,28,30,)16,20,6,18} 第6趟{(2,10,12,16,16,28,30,)20,6,18} 第7趟{(2,10,12,16,16,20,28,30,)6,18} 第8趟{(2,6,10,12,16,16,20,28,30,)18} 第9趟{(2,6,10,12,16,16,18,20,28,30)} ②折半插入排序 与①过程一样只是在比较时候比的位置不一样第一个是最后一个第二个是中间 ③希尔排序增量选取5,3,1) 增量为5:{12,2,16,30,28,10,16,20,6,18} {10,2,16,6,18,12,16,20,30,28} 增量为3:{10,2,16,6,18,12,16,20,30,28} {6,2,12,10,18,16,16,20,30,28} 增量为1:{10,2,16,6,18,12,16,20,30,28} {2,6,10,12,16,16,18,20,28,30} 二十、交换排序—冒泡/快速
1.冒泡排序
从前两两对比大的往后放
2.快速排序 例题1 设待排序的关键字序列为{12,2,16,30,28,10,16*,20,6,18}, 试分别写出使用以下排序方法 每趟排序结束后关键字序列的状态。 ①冒泡排序 {12,2,16,30,28,10,16,20,6,18} 第1趟{2, 12,16, 28, 10, 16,20,6,18,30} 第2趟{2, 12,16, 10, 16, 20, 6,18, 28,30} 第3趟{2, 12, 10, 16,16, 6,18, 20, 28,30} 第4趟{2, 10, 12, 16, 6, 16, 18, 20, 28,30} 第5趟{2, 10, 12, 6, 16,16, 18, 20, 28,30} 第6趟{2, 10, 6, 12, 16,16, 18, 20, 28,30} 第7趟{2, 6, 10, 12, 16,16, 18, 20, 28,30} 第8趟{2, 6, 10, 12, 16,16, 18, 20, 28,30} 第9趟{2, 6, 10, 12, 16,16, 18, 20, 28,30} 第10趟{2, 6, 10, 12, 16,16, 18, 20, 28,30} ②快速排序 {12,2,16,30,28,10,16,20,6,18} 第一趟 第二趟 第三趟 {2,6,10,12,18,16,16,20,28,30} 第四趟 {2,6,10,12, 16, 16,18,20,28,30} 第五趟 {2,6,10,12, 16, 16,18,20,28,30} 左子序列递归深度为1,右子序列递归深度为3 二十一、选择排序—简单选择/堆排
1. 简单选择排序
遍历找小的放前面
2. 堆排序 (1)建堆例题1 (2)重建堆堆排序过程例题1 根与最后一个元素换位置输出最后一个元素也就是根然后建堆 例题1 设待排序的关键字序列为{12,2,16,30,28,10,16*,20,6,18}, 试分别写出使用以下排序方法 每趟排序结束后关键字序列的状态。 ①简单选择排序 {12,2,16,30,28,10,16*,20,6,18} 第1趟{2, 12,16,30,28,10,16,20,6,18} 第2趟{2,6,12,16,30,28,10,16,20,18} 第3趟{2,6,10,12,16,30,28,16,20,18} 第4趟{2,6,10,12,16,30,28,16,20,18} 第5趟{2,6,10,12,16,30,28,16,20,18} 第6趟{2,6,10,12,16,16,30,28,20,18} 第7趟{2,6,10,12,16,16,18,30,28,20} 第8趟{2,6,10,12,16,16,18,20,30,28} 第9趟{2,6,10,12,16,16,18,20,28,30} 第10趟{2,6,10,12,16,16,18,20,28,30} ②堆排序 (1)初始堆 (2)重建堆 二十二、归并排序
两路归并就是两个两个排序排好之后再四个四个排以此类推 例题1 设待排序的关键字序列为{12,2,16,30,28,10,16*,20,6,18}, 试分别写出使用以下排序方法 每趟排序结束后关键字序列的状态。 ①二路归并排序 {12,2,16,30,28,10,16*,20,6,18} 第1次{2,12,16,30,10,28,16*,20,6,18} {2,12,16,30,10,28,16*,20,6,18} 第2次 {2,12,16,30,10,16*,20,28,6,18} {2,12,16,30,10,16*,20,28,6,18} 第3次{2,10,12,16,16*,20,28,30,6,18} {2,10,12,16,16*,20,28,30,6,18} 第4次{2,6,10,12,16,16*,18,20,28,30} 二十三、基数排序 例题1 给出如下关键字序列 {321,156, 57, 46, 28, 7,331, 33, 34, 63}, 试按链式基数排序方法 列出每一趟分配和收集的过程。 第一趟 分配 收集321,331,33,63,34,156,46,57,7,28 第二趟 分配 收集7,321,28,331,33,34,46,156,57,63 第三趟 分配 收集7,28,33,46,57,63,156,321,331 二十四、排序算法时间/空间/稳定性记忆
B站 BV1NL4y1t7Do
稳定性插帽龟(插入冒泡归并)统计鸡(桶排计数基数) 时间复杂度插帽龟选择帽子插选择冒泡插入的时候恩姓长老就方了n^2大喊“快归堆”快速归并堆排logn
