上午题第3章数据结构下部目录
前言
在备考软件设计师中级考试的过程中，我遇到了些许挑战，也收获了宝贵的经验。为了帮助其他同样正在为这门考试（证书）奋斗的朋友们，我决定将我的笔记整理出来，与大家分享。这些笔记不仅包含了书本上的知识，还加入了我对重点和难点的个人理解以及考试技巧，力求帮助大家更加高效地复习。我希望这份笔记能够成为你备考路上的一份支持，也祝愿你在考试中取得理想的成绩。
如果有写的不好或者需要改进的地方，恳请在评论区指正！
第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)
感谢您在万众文章中阅读了鄙人的笔记，谢谢
这份笔记由我在备考软件设计师中级考试的过程中编写，包含了我对知识点的理解与总结。如果您觉得这份笔记对您有帮助，并希望分享给更多的人，我十分乐意。但请在转载时务必注明出处，以尊重作者的劳动成果，感谢您的理解与支持。
- 每篇一句：“机会的大门永远为那些准备好自己的人敞开着：你有多努力，时光它知道”
- 如果觉得对您有用，请点个赞或者收藏鼓励我持续更新吧！
- 恭喜您，已挑战成功第三下关，请前往第四关进行挑战吧【整理中……】