2024年软件设计师中级(软考中级)详细笔记【3】数据结构(下)(分值5分)
上午题第3章数据结构下部目录
- 前言
- 第3章 数据结构【下】(5分)
- 3.5 查找
- 3.5.1 查找的基本概念【考点】
- 3.5.2 静态查找表的查找方法
- 3.5.3 动态查找表
- 3.5.4 哈希表
- 3.5.4.1 哈希表的定义
- 3.5.4.2 哈希函数的构造方法
- 3.5.4.3 处理冲突的方法
- 3.6 排序
- 3.6.1 排序的基本概念
- 3.6.2 简单排序
- 3.6.3 希尔排序
- 3.6.4 快速排序
- 3.6.5 堆排序
- 3.6.6 归并排序
- 3.6.7 基数排序
- 3.6.8 总结考点
前言
在备考软件设计师中级考试的过程中,我遇到了些许挑战,也收获了宝贵的经验。为了帮助其他同样正在为这门考试(证书)奋斗的朋友们,我决定将我的笔记整理出来,与大家分享。这些笔记不仅包含了书本上的知识,还加入了我对重点和难点的个人理解以及考试技巧,力求帮助大家更加高效地复习。我希望这份笔记能够成为你备考路上的一份支持,也祝愿你在考试中取得理想的成绩。
如果有写的不好或者需要改进的地方,恳请在评论区指正!
第3章 数据结构【下】(5分)
3.5 查找
3.5.1 查找的基本概念【考点】
静态查找表有:顺序查找,折半(二分)查找,分块查找;对查找经常要进行的两种操作是查询和检索。
动态查找表有:二叉树排序树,平衡二叉树,B_树,哈希表;对查询表经常要进行的操作是插入和删除。
- 顺序查找
- 顺序查找方法既适用于顺序存储结构,也适用于链表结构
- 顺序查找最多比较
n
次 - 顺序平均查找长度为
(n + 1)/2
- 二分查找
- 二分查找要求顺序存储,元素有序排列
- 二分查找最多比较
⌊log_2n⌋+1)
次 - 二分平均查找长度为
log_2(n+1)-1
- 二分查找去中值默认下取整,下取整没有正确答案时再考虑上取整。
3.5.2 静态查找表的查找方法
- 顺序查找
顺序查找的方法对于顺序存储方式和链式存储方式的查找表都适用。无论有序与无序。
一般情况下,c_t=n-i+1
, 因此在等概率情况下,顺序查找成功的平均查找长度为
也就是说,成功查找的平均次数约为表长的一半。与其他方法相比,顺序查找方法在,值较大时,其平均查找长度较大,查找效率较低。但这种方法也有优点,就是算法简单且适应面广,对查找表的结构没有要求,无论记录是否按关键字有序排列均可使用。
-
折半查找
折平查找要求线性表必须采用
顺序
存储结构,并且表中的数据元素接关键字有序
排列.
mid=⌊low+heigh⌋/2
折半查找的性能分析:折半查找的过程可以用一棵二叉树描述,不妨设节点总数为n=2h-1,则判定树是深度为h=log2(n+1)的满二叉树。在等概率情况下,折半查找的平均长度为当n值较大时, A S L b s ≈ l o g 2 ( n + 1 ) − 1 ASL_{bs}≈log_2(n+1)-1 ASLbs≈log2(n+1)−1。
-
下面以图17-2 为例说明折半查找算法的执行过程,设11 个有序的关键字序列为(6, 13,20,22, 37, 56, 64,76,85,88,93),要查找的K值分别为 22和 86。
在等概率情况下, P i = 1 / n P_i=1/n Pi=1/n,查找成功时折半查找的平均查找长度为: l o g 2 ( n + 1 ) − 1 log_2(n+1)-1 log2(n+1)−1
因此,折半查找的时间复杂度为 O ( l o g 2 n ) O(log_2n) O(log2n)。可见,折半查找的效率比顺序查找商,但折半查找只适用于有序表,且限于顺序存储结构。
折半查找的优点是:比较次数少,查找效率高。其缺点是:对表结构要求高,只能用于顺序存储的有序表。查找前需要排序,而排序本身是一种费时的运算。同时为了保持顺序表的有序性,对有序表进行插入和删除时,平均比较和移动表中一半元素,这也是一种费时的运算。因此,折半查找不适用于数据元素经常变动的线性表。
-
-
分块查找(了解)
分块查找又称为索引顺序查找,是对顺序查找方法的一种改进,其性能介于顺序查找和二分查找之间。
分块查找的基本思想是:在分块查找过程中,首先把表分成若干块,每一块中的关键字不一定有序,但块之间是有序的,即后一块中所有记录的关键字均大于前一个块中最大的关键字。此外,还建立了一个索引表,索引表按关键字有序。所以分块查找的过程分为两步:第一步在索引表中确定待查记录所在的块:第二步在块内顺序查找。
3.5.3 动态查找表
- 二叉排序树
- 平衡二叉树
- B-树
3.5.4 哈希表
3.5.4.1 哈希表的定义
根据设定的哈希函数和处理冲突的方法,将一组关键字映射到一个有限的、连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表称为哈希表,这一映射过程称为哈希造表或散列,所得的存储位置称为哈希地址或散列地址。
对于哈希表,主要考虑两个问题:一是如何构造哈希函数:二是如何解决冲突。
3.5.4.2 哈希函数的构造方法
常用的哈希函数构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。
除留余数法:
选择一个不大于散列表表长的正整数中,用户去除关键字,取所得的余数作为散列地址,即: H ( k e y ) = k e y % p H(key)=key\%p H(key)=key%p,p的值一般为不大于n且最接近n的质数
这个方法的关键是选取适当的p,一般情况下,可以选p为小于表长的最大质数。例如,表长为100时可取p=97。
- 点拔:除留余数法计算简单,适用范国广,是最常用的构造散列函数的方法。
关键:找合适的p,设表长为m,取p≤m且为质数
例如:{15,23,27,38,53,61,70},散列函数Hash(key)=key mod 7
对于某个哈希函数H和两个关键字K₁和K₂,如果K₁≠K₂,而H(K₁)=H(K₂),则称为冲突。具有相同哈希函数值的关键字对该哈希函数来说称为同义词。
一般情况下,冲突处理方法相同的哈希表,其平均查找长度依赖于哈希表的装填因子。哈希表的装填因子定义为 α = 表中装入的记录数 哈希表的长度 α=\frac{表中装入的记录数}{哈希表的长度} α=哈希表的长度表中装入的记录数
a标志着哈希表的装满程度。直观地看,α越小,发生冲突的可能性就越小;反之,α越大,表中已填入的记录越多,再填记录时,发生冲突的可能性就越大,则查找时,给定值需与之进行比较的关键字的个数也就越多。
3.5.4.3 处理冲突的方法
常见的处理冲突的方法有开放地址法、链地址法、再哈希法、建立一个公共溢出区。
处理冲突的方法与散列表本身的组织形式有关。按组织形式的不同,通常分两大类:开放地址法和链地址法。
-
开放地址法
开放地址法的基本思想是;把记录都存储在散列表数组中,当某一记录关键字 key 的初始散列地址H0=H(key)发生冲突时,以 H0为基础,采取合适方法计算得到另一个地址 H1,如果 H1仍然发生冲突,以H1为基础再求下一个地址 H2,若 H2仍然冲突,再求得 H3。依次类推,直至 Hk不发生冲突为止,则Hk为该记录在表中的散列地址。
这种方法在寻找“下一个"空的散列地址时,原来的数组空间对所有的元素都是开放的,所以称为开放地址法。通常把寻找“下一个”空位的过程称为探测,上述方法可用如下公式表示:
H i = ( H ( k e y ) + d i ) % m H_i = (H(key)+d_i)\%m Hi=(H(key)+di)%m i=i,2,…,k ( k ≤ m-1 )
其中,H(key)为散列函数,m为散列表表长,di为增量序列。根据di取值不同,可以分为以下3种探测方法。
-
线性探测法
d i = 1 , 2 , 3 , . . . , m − 1 d_i=1,2,3,...,m-1 di=1,2,3,...,m−1
这种探测方法可以将散列表假想成一个循环表,发生冲突时,从冲突地址的下一单元顺序寻找空单元,如果到最后一个位置也没找到空单元,则回到表头开始继续查找,直到找到一个空位,就把此元素放入此空位中。如果找不到空位,则说明散列表已满,需要进行溢出处理。
-
二次探测法
d i = 1 2 , − 1 2 , 2 2 , − 2 2 , 3 2 , . . . , k 2 , − k 2 ( k ≤ m / 2 ) d_i=1^2,-1^2,2^2,-2^2,3^2,...,k^2,-k^2 (k≤m/2) di=12,−12,22,−22,32,...,k2,−k2(k≤m/2)
-
伪随机探测法
d i = 伪随机数序列 d_i=伪随机数序列 di=伪随机数序列
-
例题:散列表的长度为11,散列函数H(key)=key%11,假设表中已填有关键字分别为17、60、29的记录,如图17-4(a)所示。现有四个记录,其关键字为38,由散列函数得到散列地址为5,使用开放地址法处理产生的冲突。
-
方法一:若用线性探测法,得到下一个地址 6;(5+1)%11=6仍冲突;再求下一个地址了,(6+1)%11=7仍冲突;直到放列地址为8的位置为“空”时为止,处理冲突的过程结束,38 镇入散列表中序号为8的位置,如用17-4(b)所示。
-
方法二:若用二次探测法,散列地址5 冲突后,得到下一个地址6,仍冲突;再求得下一个地址4,无冲突,
38 填入序号为 4的位置,如图17-4©所示。 -
方法三:若用伪随机採测法(了解),假设产生的伪随机数为9,則计算下一个放列地址为(5+9)%11=3,所以38 填入序号为3的位置,如图17-4(d)所示。
-
线性探测法、二次探测法和伪随机探测法的优缺点对比如表17-2所示。
表17-2 开放地址法优缺点
开放地址法分类 优点 缺点 线性探测法 只要散列表未填满,总能找到一个不发生冲突的地址 会产生“二次聚集”现象 二次探测法 可以避免“二次聚集”现象 不能保证一定找到不发生冲突的地址 伪随机探测法 可以避免“二次聚集”现象 不能保证一定找到不发生冲突的地址 -
点拔
从上述线性探测法处理的过程中可以看到一个现象;当表中i,i+1,i+2位置上已填有记录时,下一个散列地址为i,i+1,i+2和i+3的记录都将填入i+3的位置,这种在处理冲突过程中发生的多个第一个散列地址不同的记录争夺同一个后继散列地址的现象称作“二次聚集”(或称作“堆积”),即在处理同义词的冲突过程中又添加了非同义词的冲突。
-
3.6 排序
3.6.1 排序的基本概念
若在待排序的一个序列中,Ri和Rj~的关键字相同,即ki=kj,,且在排序前Ri领先于Rj,那么在排序后,如果Ri和Rj的相对次序保持不变,Ri仍领先于Rj,则称此类排序方法为稳定的。若在排序后的序列中有可能出现Rj领先于 Ri的情形,则称此类排序为不稳定的。
3.6.2 简单排序
-
直接插入排序
直接插入排序是一种最简单的排序方法,其基本操作是将一条记录插人到已排好序的有序表中,从而得到一个新的、记录数量增1的有序表。
-
直接插入排序步骤
例题:已知待排序记录的关键字序列为 ( 19 , 38 , 65 , 97 , 76 , 13 , 27 , 49 ‾ ) (19,38,65,97,76,13,27,\overline{49}) (19,38,65,97,76,13,27,49),请给出使用直接插入排序法进行排序的过程。
直接插入排序过程如图19-2所示,其中()中为已排好序的记录的关键字。
-
空间复杂度
直接插入排序只需要一个记录的辅助空间r[0],所以空间复杂度为O(1)
- 直接插入排序的特点
- 稳定排序
- 算法简便,且容易实现
- 也适用于链式存储结构,只是在单链表上无需移动记录,只需修改相应的指针。
- 更适合于初始记录基本有序(正序)的情况,当初始记录无序,n较大时,此算法时间复杂度较高,不宜采用。
-
-
冒泡排序
冒泡排序是一种最简单的交换排序方法,它通过两两比较相邻记录的关键字,如果发生逆序,则进行交换,从而使关键字小的记录逐浙往上“漂”(左移),或者使关键字大的记录逐渐向下“坠”(右移)。
-
冒泡排序步骤
-
例题4: 已知待排序记录的关键字序列为 ( 45 , 28 , 35 , 19 , 57 , 46 , 45 ‾ , 7 ) (45,28,35,19,57,46,\overline{45},7) (45,28,35,19,57,46,45,7),清给出使用冒泡排序法进行排
序的过程。
冒泡排序过程如图 19-4 所示,括号内表示有序区。
待排序的记录总共有8个,共进行了7趟冒泡排序。
-
-
冒泡排序的特点
- 稳定排序
- 可用于链式存储结构
- 移动记录次数较多,算法平均时间性能比直接插入排序差,当初始记录无序,n较大时,不宜采用。
-
-
简单选择排序(不稳定,归位)
简单选择排序是一种见到的选择排序方法,也称作直接选择排序。
-
简单选择排序步骤
每一趟在待排序元素中选取关键字最小的元素加入有序子序列
例题:一直待排序记录的关键字序列为 ( 49 , 38 , 65 , 97 , 49 ‾ , 13 , 27 , 76 ) (49,38,65,97,\overline{49},13,27,76) (49,38,65,97,49,13,27,76),请给出使用简单选择排序法进行排序的过程。简单选择排序过程如图19-6所示,其中()为排好序记录的关键字。
-
-
时间复杂度
简单选择排序过程中,所需进行记录移动的次数较少。最好情况(正序)下不移动;最坏情况(逆序)下移动3(n-1)次。
然而,无论记录的初始排列如何,所需进行的关键字的比较次数相同,均为: K C N = ∑ i = 1 n − 1 n − 1 = n ( n − 1 ) ≈ n 2 / 2 KCN=\sum \limits _{i = 1}^{n-1}n-1=n(n-1)≈n^2/2 KCN=i=1∑n−1n−1=n(n−1)≈n2/2
因此,简单选择排序的时间复杂度也是 O ( n 2 ) O(n^2) O(n2)。空间复杂度
同冒泡排序一样,只有在两个记录交换时需要一个辅助空间,所以空间复杂度为O(1)
-
简单选择排序的特点
- 就选择排序方法本身来讲,它是一种稳定的排序方法,但例6.中表现出来的现条是不稳定的,这是因为上述实现选择排序的算法采用“交换记录”的策路所造成的,改变这个策路,可以写出不产生“不稳定现象”的选择排序算法。
- 可用于链式存储结构
- 移动记录次数较少,当每一记录占用的空间较多时,此方法比直接插入排序快。
3.6.3 希尔排序
希尔排序又称“缩小增量排序”,是插入排序的一种。
希尔排序采用分组插入的方法,先将整个待排序记录序列分割成几组,从而减少参与直接插入排序的数据量,对每组分别进行直接插人排序,然后增加每组的数据量,重新分组。这样经过几次分组排序后,整个序列中的记录“基本有序"时,再对全体记录进行一次直接插人排序。
希尔对记录的分组,不是简单地“逐段分割”,而是将相隔某个“增量”的记录分成一组。
- 例题3 已知待排序记录的关键字序列为 49 , 38 , 65 , 97 , 76 , 13 , 27 , 49 ‾ , 55 , 04 {49,38,65,97,76,13,27,\overline{49},55,04} 49,38,65,97,76,13,27,49,55,04,请给出用希尔排序法进行排序的过程(增量选取5、3和1)
-
第一趟取增量d1=5,所有间隔为5的记录分在同一组,全部记最分成5组,在各个组中分别进行直接插入排序。
-
第二趟取增量d2=3,所有间隔为3的记录分在同一组,全部记录分成3组,在各个組中分别进行直接插入排序。
-
第三趟取增量d3=1,对整个序列进行一趟直接插入排序,排序完成。
希尔排序过程如图19-3所示
3.6.4 快速排序
快速排序是由冒泡排序改进而来的。在冒泡排序过程中,只对相邻的两个记录进行比较,因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个(不相邻)记录的一次交换,消除多个逆序,则会大大加快排序的速度。
-
快速排序步骤
在待排序的n 个记录中任取一个记录(通常取第一个记录)作为枢轴(或支点),设其关键字为 pivotkey.经过一趟排序后,把所有关键字小于 pivotkey 的记录交换到前面,把所有关键字大于 pivotkey 的记录交换到后面,结果将待排序记录分成两个子表,最后将枢轴放置在分界处的位置。然后,分别对左、右子表重复上述过程,直至每一子表只有一个记录时,排序完成。
其中,一趟快速排序的具体步骤如下:
①选择待排序表中的第一个记录作为枢轴,将枢轴记录存在r[0]的位置上。附设两个指针 low 和high,初始时分别指向表的下界和上界(第一趟时,low=1,high= L. length;)
②从表的最右侧位置依次向左搜索,找到第一个关键字小于枢轴关键字 pivotkey 的记录,将其移到 low处。具体操作是:当 low<high 时,若 high 所指记录的关键字大于等于 pivotkey,则向左移动指针high(执行操作 high一1);否则将 high 所指记录与枢轴记录交换。
③然后再从表的最左侧位置,依次向右搜索找到第一个关键字大于 pivotkey 的记录和枢轴记录交换。具体操作是;当 low<high 时,若 low 所指记录的关键字小于等于 pivotkey,则向右移动指针 low(执行操作low+1);否则将 low 所指记录与枢轴记录交换。
④重复步骤②和③,直至 low 与 high 相等为止。此时 low 或 high 的位置即为枢轴在此趟排序中的最终位置,原表被分成两个子表。
-
点拔
-
在上进过程中,记承的交换都是与都軸之问发生的,每次交换都要移动3次记录,可以先特枢轴记录暫存在 r0]的位置上,排序过程中只移动要与枢轴交換的记录,即只做-low]或 -[high]的单向移动,直至一趟排序结束后再将极轴记录移至正确位置上。
-
例题: 已知待排序记录的关键字序列为 ( 49 , 38 , 65 , 97 , 76 , 13 , 27 , 49 ‾ ) (49,38,65,97,76,13,27,\overline{49}) (49,38,65,97,76,13,27,49),请给出使用快速排序法进行排序的过程。
-
第一趟快速排序过程如图19-5(a)所示,整个快速排序的过程如图19-5(b)所示。
-
-
算法
算法分析:
-
时间复杂度
最好情况下每一趟排序后都能将记录序列均匀地分割成两个长度大致相等的子表(每次总是选到中间值作为枢轴),总的排序时间 T(n)=O(nlog2n),最坏情况下每次划分只能得到一个比上一次少一个记录的子序列(每次总是选到最大或最小的元素作为枢轴),T(n)=O(n2)。平均情况下,快速排序的时间复杂度为 O(nlog2n)。
-
空间复杂度
快速排序是递归的,需要一个栈来存放数据。最好情况下的空间复杂度为 O(log2n),最坏情况下的空间复杂度为 O(n)。
-
快速排序算法的特点
- 由于记录的移动是非顺次的,所以快速排序是一种不稳定的排序方法。
- 由于在排序过程中需要定位表的上界和下届,所以适用于顺序结构,很难用于链式结构。
- 适用于初始记录无序、记录较多的情况。在记录较多时,在平均情况下快速排序是所有内部排序方法中速度最快的一种。
-
3.6.5 堆排序
对于n个元素的关键字序列 K 1 , K 2 , … … , K n {K_1,K_2,……,K_n} K1,K2,……,Kn,当且仅当满足下列关系时称其为堆,其中2i+1应不大于n。
-
堆的定义
n个元素的序列 k 1 , k 2 , . . . , k n − 1 , k n {k_1,k_2,...,k_{n-1},k_n} k1,k2,...,kn−1,kn当且仅当满足以下条件时称之为堆:
{ k i ≥ k 2 i k i ≥ k 2 i + 1 \begin{cases} k_i\geq k_{2i}\\ k_i\geq k_{2i+1} \end{cases} {ki≥k2iki≥k2i+1
或
{ k i ≤ k 2 i k i ≤ k 2 i + 1 其中 i = 1 , 2 , 3 … ⌊ n / 2 ⌋ (1) \begin{cases} k_i\leq k_{2i}\\ k_i\leq k_{2i+1} \end{cases} 其中i=1,2,3\dots⌊n/2⌋ \tag{1} {ki≤k2iki≤k2i+1其中i=1,2,3…⌊n/2⌋(1)
若将和此序列对应的一维数组(即以一维数组做此序列的存储结构)看成是一个完全二叉树,则堆实质上是满足如下性质的完全二叉树:树中所有非终端结点的值均不大于(或均不小于)其左、右孩子结点的值。例如,关键字序列(96,83,27,38,11,09}和(12,36,24,85,47,30,53,91}均为堆,对应的完全二叉树分别如图 19-7(a)和 19-7(b)所示。显然,在这两种堆中,堆顶元素(或完全二叉树的根)必为序列中n个元案的最大值(或最小值),分别称之为大根堆(或小根堆)。
-
堆排序步骤
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特种,使得当前无序的序列中选择关键字最大(或最小)的记录变得简单。大根堆排序的步骤如下:
-
调整堆
图19-8(a)是个堆,将堆顶元素97 和堆中最后一个元紫38 交换后,如图 19-8(b)所示。由于此时除根结点外,其余结点均满足堆的性质,由此仅需自上至下进行一条路径上的结点调整即可。首先以堆顶元素38 和其左、右子树根结点的值进行比较,由于左子树根结点的值大于右子树根结点的值且大于根结点的值,则将 38和76 交换;由于38 替代了 76 之后破坏了左子树的“堆”,则需对左子树进行和上述相同的调整,直至叶子结点,调整后的状态如图 19-8©所示。
上述过程就像过筛子一样,把较小的关键宇逐层筛下去,而将较大的关键字逐层选上米。因此,称此方法为“筛选法”。
-
建初堆
要将一个无序序列调整为堆,就必须将其所对应的完全二叉树中以每一结点为根的子树都调整为堆。
显然,只有一个结点的树必是堆,而在完全二叉树中,所有序号大于⌊n/2⌋的结点都是叶子,因此以这些结点为根的子树均已是堆。这样,只需利用筛选法,从最后一个分支结点⌊n/2⌋开始,依次将序号为⌊n/2⌋、⌊n/2⌋-1、⋯、1 的结点作为根的子树都调整为堆即可。- 例题7:已知无序序列为(49,38,65,97,76,13,27,49},用“筛选法”将其调整为一个大根堆,给出建堆的过程。
从图 19-9(a)所示的无序序列的最后一个非终端结点开始筛选,即从第4个元素97开始,由于97>49,則无须交换。同理,第3个元素65不小于共左、右子树根的值,仍无须交换。而第2个元素38<97,被筛选之后序列的状志如因 19-9(b)所示,然后对根元素49筛选之后得到园 19-9©所示的大根堆。
- 例题7:已知无序序列为(49,38,65,97,76,13,27,49},用“筛选法”将其调整为一个大根堆,给出建堆的过程。
-
-
堆排序实例
根据前面堆排序算法步骤的描述,可知堆排序就是将无序序列建成初堆以后,反复进行交换和堆调整。
- 例9 一直待排序记录的关键字序列为 { 49 , 38 , 65 , 97 , 76 , 13 , 27 , 49 ‾ } \{49,38,65,97,76,13,27,\overline{49}\} {49,38,65,97,76,13,27,49},请给出使用堆排序法继续排序的过程。
- 首先对无序序列建初堆,过程如因 19-9 所示。在初始大根堆的基础上,反复交换堆顶元素和最后一个元素,然后重新调整堆,直至最后得到一个有序序列,整个堆排序过程如园 19-10 所示。
-
堆排序的特点
- 不稳定排序。
- 只能用于顺序结构,不能用于链式结构。
- 初始建堆所需的比较次数较多,因此记录数较少时不宜采用。堆排序在最坏情况下时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n),相对于快速排序最坏情况下的 O ( n 2 ) O(n^2) O(n2)而言是一个优点,当记录较多时较为高效。空间复杂度为 O(1)。
3.6.6 归并排序
归并排序就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并,2-路归并最为简单和常用。下面以2-路归并为例,介绍归并排序算法。
-
归并排序的过程
把两个或多个已经有序的序列合并成一个- 假设初始序列含有n个记录,则可看成是n个有序的子序列,每个子序列的长度为1。
- 两两归并,得到⌈n/2⌉个长度为2或1的有序子序列。(⌈⌉向上取整)
- 再两两归并,⋯,如此重复,直至得到一个长度为n的有序序列为止。
- 例9 已知待排序记乘的关健字序列为{49,38,65,87,76,13,27},请给出使月2-路归井排序法进行排序的过程。
2-路归并排序的过程如图 19-11 所示。
-
时间复杂度
当有n个记录时,需进行 ⌈ l o g 2 n ⌉ ⌈log_2n⌉ ⌈log2n⌉趟归并排序,每一趟归并,共关键字比较次数不超过n,元素移动次数都是n,因此,归并排序的时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) -
空间复杂度
用顺序表实现归并排序时,需要和待排序记录个数相等的辅助存储空间,所以空间复杂度为O(n)。 -
归并排序的特点
- 稳定排序
- 可用于链式结构,且不需要附加存储空间,但递归实现时仍需要开辟相应的递归工作栈。
3.6.7 基数排序
基数排序的思想是:设立,个队列,队列的编号分别为0,12.⋯r-1。首先按最低有效位的值,把n个关键字分配到这,个队列中;然后从小到大将各队列中关键字再依次收集起来:接着按次低有效位的值把刚收集起来的关键字再分配到,个队列中。重复上述收集过程,直至最高有效位,这样得到了一个从小到大有序的关键字序列。为了减少记录移动的次数,队列可以采用链式存储分配,称为链队列。每个链队列设有两个指针,分别指向队头和队尾。
对于n个记录,执行一次分配和收集的时间为O(n +r),如果关键字有d位,则要执行d 遍,所以总的运算时间为O(d(n+r))。基数排序适用于链式分配的记录的排序,是一种稳定的排序方法。
3.6.8 总结考点
下面从时间复杂度、空间复杂度和稳定性几个方面对内部排序方法做比较,结果如下表所示。
主要记简单选择排序和堆排序的时间、空间复杂度和稳定性。
从上表的时间复杂度的平均情况来看,直接插人排序、冒泡排序和简单选择排序的速度较慢,而其他排序方法的速度较快。从算法实现的角度来看,速度较慢的算法实现过程比较简单,称之为简单的排序方法;而速度较快的算法可以看作是对某一排序算法的改进,称之为先进的排序方法,但这些算法实现过程比较复杂。总的来看,各种排序算法各有优缺点,没有哪一种是绝对最优的。在使用时需根据不同情况适当选用,甚至可将多种方法结合起来使用。一般综合考虑以下因素:
(1) 待排序的记录个数;
(2) 记录本身的大小;
(3) 关键字的结构及初始状态;
(4) 对排序稳定性的要求;
(5) 存储结构
根据这些因素和商标所做的比较,可以得出以下几点结论:
(1)当待排序的记录个数n较小时, n 2 n^2 n2和 n l o g 2 n nlog_2n nlog2n 的差别不大,可选用简单的排序方法。而当关键字基本有序时,可选用直接插入排序或冒泡排序,排序速度很快,其中直接插入排序最为简单常用、性能最佳。
(2)当n较大时,应该选用先进的排序方法。对于先进的排序方法,从平均时间性能而言,快速排序最佳,是目前基于比较的排序方法中最好的方法。但在最坏情况下,即当关键字基本有序时,快速排序的递归深度为n,时间复杂度为 O ( n 2 ) O(n^2) O(n2),空间复杂度为O(n)
。堆排序和归并排序不会出现快速排序的最坏情况,但归并排序的辅助空向较大。这样,当n较大时,具体选用的原则是:
①当关键字分布随机,稳定性不做要求时,可采用快速排序;
②当关键字基本有序,稳定性不做要求时,可采用堆排序;
③当关键字基本有序,内存允许且要求排序稳定时,可采用归并排序。
- 简单选择排序和堆排序都是在一次排序后就确定一个元素的最终位置
- 快速排序是一种基于分治的算法,每趟排序可以确定一个元素的最终位置(即归位)。
- 快速排序最坏的情况是待排序序列基本有序,时间复杂度为 O ( n 2 ) O(n^2) O(n2) ,空间复杂度为O(n)
- 以第一个元素为基准元素就 先从后往前找 再从前往后找
- 以最后一个元素为基准元素就 先从前往后找 再从后往前找
- 归并排序采用分治的算法策略
- 归并排序的时间复杂度直接记 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n),空间复杂度 O ( l o g 2 n ) O(log_2n) O(log2n)
感谢您在万众文章中阅读了鄙人的笔记,谢谢
这份笔记由我在备考软件设计师中级考试的过程中编写,包含了我对知识点的理解与总结。如果您觉得这份笔记对您有帮助,并希望分享给更多的人,我十分乐意。但请在转载时务必注明出处,以尊重作者的劳动成果,感谢您的理解与支持
。
- 每篇一句:“机会的大门永远为那些准备好自己的人敞开着:你有多努力,时光它知道”
- 如果觉得对您有用,请点个赞或者收藏鼓励我持续更新吧!
- 恭喜您,已挑战成功第三下关,请前往第四关进行挑战吧【点击即可跳转】
相关文章:

2024年软件设计师中级(软考中级)详细笔记【3】数据结构(下)(分值5分)
上午题第3章数据结构下部目录 前言第3章 数据结构【下】(5分)3.5 查找3.5.1 查找的基本概念【考点】3.5.2 静态查找表的查找方法3.5.3 动态查找表3.5.4 哈希表3.5.4.1 哈希表的定义3.5.4.2 哈希函数的构造方法3.5.4.3 处理冲突的方法 3.6 排序3.6.1 排序的基本概念3.6.2 简单排…...

WPF|依赖属性SetCurrentValue方法不会使绑定失效, SetValue方法会使绑定失效?是真的吗?
引言 最近因为一个触发器设置的结果总是不起效果的原因,进一步去了解[依赖属性的优先级](Dependency property value precedence - WPF .NET | Microsoft Learn)。在学习这个的过程中发现对SetCurrentValue一直以来的谬误。 在WPF中依赖属性Dependency property的…...

Windows搭建Java开发环境(Building a Java development environment on Windows)
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:Linux运维老纪的首页…...

用FPGA做一个全画幅无反相机
做一个 FPGA 驱动的全画幅无反光镜数码相机是不是觉得很酷? 就是上图这样。 Sitina 一款开源 35 毫米全画幅 (3624 毫米) CCD 无反光镜可换镜头相机 (MILC),这个项目最初的目标是打造一款数码相机,将 SLR [单镜头反光] 相机转换为 DSLR [数码…...

使用 Go 语言与 Redis 构建高效缓存与消息队列系统
什么是 Redis? Redis 是一个开源的内存数据库,支持多种数据结构,包括字符串、列表、集合、哈希和有序集合。由于 Redis 运行在内存中,读写速度极快,常被用于构建缓存系统、实时排行榜、会话存储和消息队列等高并发场景…...

springboot 整合spring ai实现 基于知识库的客服问答
rag 需求产生的背景介绍: 在使用大模型时,常遇到的问题之一是模型可能产生幻觉,即生成的内容缺乏准确性。此外,由于大模型不直接访问企业的专有数据,其响应可能会显得泛泛而谈,不够精准或具体,…...

云原生(四十九) | WordPress源码部署
文章目录 WordPress源码部署 一、WordPress部署步骤 二、创建项目目录 三、上传源码到WordPress 四、配置安全组 五、配置WordPress 六、访问WordPress WordPress源码部署 一、WordPress部署步骤 第一步:创建项目目录 第二步:上传源码到项目目…...

Spring Boot 集成 LiteFlow 实现业务流程编排
LiteFlow 是一款轻量级的流程编排框架,它允许开发者通过简单的配置方式,将复杂的业务流程分解为多个独立的节点,然后通过定义规则来编排节点,达到解耦业务逻辑、提高代码可维护性的目的 1. LiteFlow 的基本概念 在 LiteFlow 中,主要有以下几个概念: 节点 (Node):代表一…...
在 Android Studio 中引入android.os.SystemProperties
在 Android Studio 中引入android.os.SystemProperties 前言 网上有很多种方法,其中直接导入包的办法是行不通的,昨天自己发现问题后也踩了很多坑,现在把问题解决了也全面汇总了几种方法,确保可以百分百引入 1. layoutlib.jar包…...
代码随想录算法训练营总结
这几天一直有事情需要忙,所以现在来准备总结以下训练营的成果。 先说以下总体感受,非常值得!!! 从两个月前开始跟着每天看发布的任务,然后每天坚持打卡,收获还是很大的,从数组开始…...

【uniapp】使用uniapp实现一个输入英文单词翻译组件
目录 1、组件代码 2、组件代码 3、调用页面 4、展示 前言:使用uniapp调用一个在线单词翻译功能 1、组件代码 2、组件代码 YouDaoWordTranslator <template><view class"translator"><input class"ipttext" type"te…...

6. 继承、重写、super、final
文章目录 一、重新定义需求二、继承1. 继续分析2. 概念3. 代码① 父类② 子类③ 测试结果 4. 饿狼传说之多层继承① 概念② 代码 5. 多继承 三、方法的重写1. 情境2. 代码① 吃什么② 怎么叫(Override重写) 3. 小结 四、super1. 啃老2. 啃老啃到底 五、final1. 用途及特征2. 举…...

Redis 其他类型 渐进式遍历
我们之前已经学过了Redis最常用的五个类型了,然而Redis还有一些在特定场景下比较好用的类型 Redis最关键的五个数据类型: 上面的类型是非常常用,很重要的类型。 除此之外的其他类型不常用,只是在特定的场景能够发挥用处&#…...

科研绘图系列:R语言绘制SCI文章图2
文章目录 介绍加载R包导入数据图a图b图d系统信息介绍 文章提供了绘制图a,图b和图d的数据和代码 加载R包 library(ggplot2) library(dplyr) library(readxl) library(ggpmisc)导入数据 数据可从以下链接下载(画图所需要的所有数据): 百度网盘下载链接: https://pan.baid…...

ARM知识点三和串口代码的编写流程
ARM的一些常见问题 ARM 体系结构的主要特点是什么? 精简指令集 (RISC):ARM 采用 RISC 结构,指令集较小且简单,执行效率高。相比于复杂指令集 (CISC),RISC 更强调每条指令的执行速度。低功耗设计:ARM 处理…...

【unity踩坑】打开vs2022没有文字联想/杂项文件
unity打开vs2022没有文字联想 修改外置编辑器安装unity开发插件vs编辑器显示杂项文件 修改外置编辑器安装unity开发插件 参考 在unity项目里选择Edit-> Preferences->External Tools然后更换编辑器 在vs工具界面添加unity游戏开发选项。 重新打开还是有问题ÿ…...

WebGoat JAVA反序列化漏洞源码分析
目录 InsecureDeserializationTask.java 代码分析 反序列化漏洞知识补充 VulnerableTaskHolder类分析 poc 编写 WebGoat 靶场地址:GitHub - WebGoat/WebGoat: WebGoat is a deliberately insecure application 这里就不介绍怎么搭建了,可以参考其他…...

大数据-161 Apache Kylin 构建Cube 按照日期、区域、产品、渠道 与 Cube 优化
点一下关注吧!!!非常感谢!!持续更新!!! 目前已经更新到了: Hadoop(已更完)HDFS(已更完)MapReduce(已更完&am…...

uni-app使用v-show编译成微信小程序的问题
问题 在uni-app使用v-show语法编译成微信小程序会有一个问题 当我们设置成v-show"false" 在Hbuilder X里面确实没有显示 然后运行到 微信开发程序里面 发现显示了出来,说明设置的 v-show"false"没有起作用 解决办法 首先去uniapp官网查看v…...

充电宝租赁管理系统网站毕业设计SpringBootSSM框架开发
目录 1. 概述 2. 技术选择与介绍 3. 系统设计 4. 功能实现 5. 需求分析 1. 概述 充电宝租赁管理系统网站是一个既实用又具有挑战性的项目。 随着移动设备的普及和人们日常生活对电力的持续依赖,充电宝租赁服务已成为现代都市生活中的一项重要便利设施。它不仅为…...

遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...

七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...