（计算机基础 核心知识）数据结构（21-40）

21.排序算法

冒泡排序

两个数比较大小，较大的数下沉，较小的数冒起来。

冒泡排序算法的原理如下：

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

有很多人说冒泡排序的最优的时间复杂度为：O(n)；其实这是在代码中使用一个标志位来判断是否已经排序好的，修改下上面的排序代码：

 void bubbleSort(int array[], int length)
 {
     int i, j, tmp;
     int flag = 1;
     
     if (1 >= length) return;
 
     for (i = length-1; i > 0; i--, flag = 1){ 
         for (j = 0; j < i; j++){
             if (array[j] > array[j+1]){
                 tmp        = array[j];
                 array[j]   = array[j+1];
                 array[j+1] = tmp;
                 flag = 0;
             }   
         }   
         //如果一次都没有交换，说明有序，可以直接退出
         if (flag) break;
     }   
 }

根据上面的代码可以看出，如果元素已经排序好，那么循环一次就直接退出。或者说元素开始就已经大概有序了，那么这种方法就可以很好减少排序的次数

选择排序

直接选择排序：每次在未排序序列中找到最小元素，和未排序序列的第一个元素交换位置，再在剩余未排序序列中重复该操作直到所有元素排序完毕。

时间复杂度 O(n²)，空间复杂度 O(1)。

选择排序(Selection sort)是一种简单直观的排序算法。其基本思想是：首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

以数列{20,40,30,10,60,50}为例，演示其选择排序过程(如下图)。

第1趟：i=0。找出a[1...5]中的最小值a[3]=10，然后将a[0]和a[3]互换。 数组变化：20,40,30,10,60,50 -- > 10,40,30,20,60,50

第2趟：i=1。找出a[2...5]中的最小值a[3]=20，然后将a[1]和a[3]互换。 数组变化：10,40,30,20,60,50 -- > 10,20,30,40,60,50

第3趟：i=2。找出a[3...5]中的最小值，由于该最小值大于a[2]，该趟不做任何处理。

第4趟：i=3。找出a[4...5]中的最小值，由于该最小值大于a[3]，该趟不做任何处理。

第5趟：i=4。交换a[4]和a[5]的数据。 数组变化：10,20,30,40,60,50 -- > 10,20,30,40,50,60

归并排序

归并排序：将待排序序列分成两部分，然后对两部分分别递归排序，最后进行合并。 排序算法稳定，时间复杂度都为 O(nlogn)，空间复杂度为 O(n)。

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

① 将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素 ② 将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素 ③ 重复步骤②，直到所有元素排序完毕

上图中首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。

不管元素在什么情况下都要做这些步骤，所以花销的时间是不变的，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为：O( nlogn )

并不会发生相同元素的相对位置发生变化，故是稳定性算法。

计数排序

计数排序不是一个比较排序算法，该算法于1954年由 Harold H. Seward提出，通过计数将时间复杂度降到了O(N)。

第一步：找出原数组中元素值最大的，记为max。

第二步：创建一个新数组count，其长度是max加1，其元素默认值都为0。

第三步：遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。

第四步：创建结果数组result，起始索引index。

第五步：遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值不大于0，依次处理count中剩下的元素。

第六步：返回结果数组result。

基础版能够解决一般的情况，但是它有一个缺陷，那就是存在空间浪费的问题。

比如一组数据{101,109,108,102,110,107,103}，其中最大值为110，按照基础版的思路，我们需要创建一个长度为111的计数数组，但是我们可以发现，它前面的[0,100]的空间完全浪费了，那怎样优化呢？

将数组长度定为max-min+1，即不仅要找出最大值，还要找出最小值，根据两者的差来确定计数数组的长度。

作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序不是比较排序，排序的速度快于任何比较排序算法

桶排序

其实桶排序重要的是它的思想，而不是具体实现，桶排序从字面的意思上看：

• 桶：若干个桶，说明此类排序将数据放入若干个桶中。
• 桶：每个桶有容量，桶是有一定容积的容器，所以每个桶中可能有多个元素。
• 桶：从整体来看，整个排序更希望桶能够更匀称，即既不溢出(太多)又不太少。

工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

• 将待排序的序列分到若干个桶中，每个桶内的元素再进行个别排序。
• 时间复杂度最好可能是线性O(n)，桶排序不是基于比较的排序

当然，桶排序是一种用空间换取时间的排序。

既然是排序，那么最终的结果肯定是从小到大的，桶排序借助桶的位置完成一次初步的排序——将待排序元素分别放至各个桶内。

而我们通常根据待排序元素整除的方法将其较为均匀的放至桶中，如8 5 22 15 28 9 45 42 39 19 27 47 12这个待排序序列，假设放入桶编号的规则为：n/10。这样首先各个元素就可以直接通过整除的方法放至对应桶中。而右侧所有桶内数据都比左侧的要大！

在刚刚放入桶中的时候，各个桶的大小相对可以确定，右侧都比左侧大，但桶内还是无序的，对各个桶内分别进行排序，再依次按照桶的顺序、桶内序列顺序得到一个最终排序的序列。

桶排序的时间复杂度到底是多少？

我们假设有n个待排序数字。分到m个桶中，如果分配均匀这样平均每个桶有n/m个元素。首先在这里我郑重说明一下桶排序的算法时间复杂度有两部分组成：

• 1.遍历处理每个元素，O(n)级别的普通遍历
• 2.每个桶内再次排序的时间复杂度总和

对于第一个部分，我想大家都应该理解最后排好序的取值遍历一趟的O(n);而第二部分咱们可以进行这样的分析：

• 如果桶内元素分配较为均匀假设每个桶内部使用的排序算法为快速排序，那么每个桶内的时间复杂度为(n/m) log(n/m)。有m个桶，那么时间复杂度为m * (n/m)log(n/m)=n (log n-log m).

在这里如果到达极限情况n=m时。就能确保避免桶内排序，将数值放到桶中不需要再排序达到O(n)的排序效果,当然这种情况属于计数排序，后面再详解计数排序记得再回顾。

桶排序并且像常规排序那样没有限制，桶排序有相当的限制。因为桶的个数和大小都是我们人为设置的。而每个桶又要避免空桶的情况。所以我们在使用桶排序的时候即需要对待排序数列要求偏均匀，又要要求桶的设计兼顾效率和空间。

待排序序列要求均匀？我要不均匀又会怎么样呢？ 会这样：

这才短短不到100个数，你为了一一映射用100000个空间，空间内容浪费不说，你遍历虽然O(n)也是100000次也比100个的O(nlogn)大上很多啊，真是折了夫人又折兵。

所以现在明白前面说的话了吧：数要相对均匀分布，桶的个数也要合理设计。总之桶排序是一种用空间换取时间的排序。在设计桶排序，你需要知道输入数据的上界和下界，看看数据的分布情况，再考虑是否用桶排序，当然如果能用好桶排序，效率还是很高的！

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异

• 基数排序：根据键值的每位数字来分配桶；
• 计数排序：每个桶只存储单一键值；
• 桶排序：每个桶存储一定范围的数值

① 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。 ② 从最低位开始，依次进行一次排序。 ③ 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

分步图示说明：设有数组 array = {53, 3, 542, 748, 14, 214, 154, 63, 616}，对其进行基数排序：

在上图中，首先将所有待比较数字统一为统一位数长度，接着从最低位开始，依次进行排序。

• 按照个位数进行排序。
• 按照十位数进行排序。
• 按照百位数进行排序。

排序后，数列就变成了一个有序序列。

设待排序的数组R[1..n]，数组中最大的数是d位数，基数为r（如基数为10，即10进制，最大有10种可能，即最多需要10个桶来映射数组元素）。

处理一位数，需要将数组元素映射到r个桶中，映射完成后还需要收集，相当于遍历数组一遍，最多元素数为n，则时间复杂度为O(n+r)。所以，总的时间复杂度为O(d*(n+r))。

基数排序基于分别排序，分别收集，所以是稳定的。

上面我们发现：如果将桶按顺序进行回收，那么我们的排序就完成了～

可是，一般我们的数组元素都不仅仅是个位数的数字的呀，那么高位数的数字又怎么弄呢？？比如：23,44,511,6234这些高位数..

其实也是一样的：

• 第一趟桶排序将数字的个位数分配到桶子里面去，然后回收起来，此时数组元素的所有个位数都已经排好顺序了
• 第二趟桶排序将数字的十位数分别分配到桶子里面去，然后回收起来，此时数组元素的所有个位数和十位数都已经排好顺序了(如果没有十位数、则补0)
• 第三趟桶排序将数字的百位数分别分配到桶子里面去，然后回收起来，此时数组元素的所有个位数和十位数和百位数都已经排好顺序了(如果没有百位数、则补0)

希尔排序

那么，怎样可以对插入排序算法做出优化呢？我们不妨从插入排序的两个特点入手：

1.在大多数元素已经有序的情况下，插入排序的工作量较小

这个结论很明显，如果一个数组大部分元素都有序，那么数组中的元素自然不需要频繁地进行比较和交换。

2.在元素数量较少的情况下，插入排序的工作量较小

这个结论更加显而易见，插入排序的工作量和n的平方成正比，如果n比较小，那么排序的工作量自然要小得多。

如何对原始数组进行预处理呢？聪明的科学家想到了一种分组排序的方法，以此对数组进行一定的“粗略调整”。

所谓分组，就是让元素两两一组，同组两个元素之间的跨度，都是数组总长度的一半，也就是跨度为4。

如图所示，元素5和元素9一组，元素8和元素2一组，元素6和元素1一组，元素3和元素7一组，一共4组。

接下来，我们让每组元素进行独立排序，排序方式用直接插入排序即可。由于每一组的元素数量很少，只有两个，所以插入排序的工作量很少。每组排序完成后的数组如下：

这样一来，仅仅经过几次简单的交换，数组整体的有序程度得到了显著提高，使得后续再进行直接插入排序的工作量大大减少。这种做法，可以理解为对原始数组的“粗略调整”。

但是这样还不算完，我们可以进一步缩小分组跨度，重复上述工作。把跨度缩小为原先的一半，也就是跨度为2，重新对元素进行分组：

如图所示，元素5，1，9，6一组，元素2，3，8，7一组，一共两组。

接下来，我们继续让每组元素进行独立排序，排序方式用直接插入排序即可。每组排序完成后的数组如下：

此时，数组的有序程度进一步提高，为后续将要进行的排序铺平了道路。

最后，我们把分组跨度进一步减小，让跨度为1，也就等同于做直接插入排序。经过之前的一系列粗略调整，直接插入排序的工作量减少了很多，排序结果如下：

像这样逐步分组进行粗调，再进行直接插入排序的思想，就是希尔排序

**上面示例中所使用的分组跨度（4，2，1），被称为希尔排序的增量，**增量的选择可以有很多种，我们在示例中所用的逐步折半的增量方法

希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多。

22.数组和链表的区别

从逻辑结构上来说，这两种数据结构都属于线性表。所谓线性表，就是所有数据都排列在只有一个维度的“线”上，就像羊肉串一样，把数据串成一串。对其中任意一个节点来说，除了头尾，只有一个前趋，也只有一个后继。

从物理上来说，即在内存中，这两种逻辑结构所对应的物理存储分布上看，数组占用的是一块连续的内存区，而链表在内存中，是分散的，因为是分散的，就需要一种东西把他们串起来，这样才能形成逻辑上的线性表，不像数组，与生俱来具有“线性”的成分。因为链表比数组多了一个“串起来”的额外操作，这个操作就是加了个指向下个节点的指针，所以对于链表来说，存储一个节点，所要消耗的资源就多了。也正因为这种物理结构上的差异，导致了他们在访问、增加、删除节点这三种操作上所带来的时间复杂度不同。

对于访问，数组在物理内存上是连续存储的，硬件上支持“随机访问”，所谓随机访问，就是你访问一个a[3]的元素与访问一个a[10000]，使用数组下标访问时，这两个元素的时间消耗是一样的。但是对于链表就不是了，链表也没有下标的概念，只能通过头节点指针，从每一个节点，依次往下找，因为下个节点的位置信息只能通过上个节点知晓（这里只考虑单向链表），所以访链表中的List(3)与List(10000)，时间就不一样了，访问List(3)，只要通过前两个节点，但要想访问List(10000)，不得不通过前面的9999个节点；而数组是一下子就跳到了a[10000]，无需逐个访问a[10000]之前的这些个元素。所以对于访问，数组和链表时间复杂度分别是O(1)与O(n)，方式一种是“随机访问”，一种是“顺序访问”。

对于增加，因为数组在内存中是连续存储的，要想在某个节点之前增加，且保持增加后数组的线性与完整性，必须要把此节点往后的元素依次后移。要是插在第一个节点之前，那就GG了，数组中所有元素位置都得往后移一格，最后把这个后来的“活宝元素”，稳稳的放在第一个腾出来的空闲位置上，真是不考虑其他元素的感受，就像我们日常生活排队时，出现的“加塞”现象一样。“加塞”位置前的人没什么意见，因为他们的领先位置没动，还是按原来的顺序先到先得的享受服务，“加塞”位置后的人就有意见了，他们不得不都往后挪一个位置，很有可能面对突然的后挪，踩到后面人的脚，享受服务的顺序也往后挪了一位。对于数组来说，有“加塞”时，一定要先做好数据迁移，不然就会踩到脚，数组元素丢了，而且数组下标也要往后+1，享受服务的顺序往后推了一位。

而链表却为其他元素着想多了。由上图可知，链表中只需要改变节点中的“指针”，就可以实现增加。自身在内存中所占据的位置不变，只是这个节点所占据的这块内存中数据（指针）改变了，相对于数组“牵一发而动全身”的大动作，链表则要显示温和的多，局部数据改写就可以了。如下图所示：

对于数组与链表的节点删除操作，同理。

除了访问、插入、删除的不同外，还有在操作系统内存管理方面也有不同。正因为数组与链表的物理存储结构不同，在内存预读方面，内存管理会将连续的存储空间提前读入缓存（局部性原理），所以数组往往会被都读入到缓存中，这样进一步提高了访问的效率，而链表由于在内存中分布是分散的，往往不会都读入到缓存中，这样本来访问效率就低，这样效率反而更低了。在实际应用中，因为链表带来的动态扩容的便利性，在做为算法的容器方面，用的更普遍一点。

数组的使用需要事先在内存中分配一块连续的地址空间，数组中的元素在内存中连续存放，它支持随机访问（给出数组首地址和查找元素的下标就可以直接访问该元素），不过在数组中插入和删除操作需要移动大量的元素。 链表的使用不用事先在内存分配地址空间，链表中的元素在内存中不是顺序存储的，只能支持顺序访问，对于元素的插入和删除操作不需移动元素，只需更改一些节点指针即可。

23.二分查找可以用链表实现吗

因为链表的每一个节点的地址不能在O(1)的时间复杂度内获得

可以看到，在数组（线性表）中，a[i]的地址就是 &a[0]+sizeof(int)*i （a+i）

这样你对于一次二分查找 [l,r) 区域，我可以通过简单的计算得到中间值 mid = (l+r)/2 对应的值

而对于链表，每个节点对应的坐标是不确定的，比如查找 [0,4) ，我需要比较mid = （0+4）/2 = 2 的值

然后电脑就开始找，从0开始往后找到1，找到1再往下找……经过千辛万苦才能找到 a[2] 位于0x0010 这个地址

理论而言，我们每次都需要遍历整个查询区域二分之一长度的数据，也即 T(n/2)

再加上二分查找本身的 T(logn) 总的时间复杂度是 O(nlogn) 甚至比你直接遍历链表查询更慢！

24.数据结构的复杂度o(1)是什么意思

时间复杂度O(n)，表示程序运行时间跟n有关，并且是线性关系。 空间复杂度O(1)，表示所需辅助空间为常量，并且与n无关

25.函数调用

在main函数调用func_A的时候，首先在自己的栈帧中压入函数返回地址，然后为func_A创建新栈帧并压入系统栈 在func_A调用func_B的时候，同样先在自己的栈帧中压入函数返回地址，然后为func_B创建新栈帧并压入系统栈 在func_B返回时，func_B的栈帧被弹出系统栈，func_A栈帧中的返回地址被“露”在栈顶，此时处理器按照这个返回地址重新跳到func_A代码区中执行 在func_A返回时，func_A的栈帧被弹出系统栈，main函数栈帧中的返回地址被“露”在栈顶，此时处理器按照这个返回地址跳到main函数代码区中执行

ESP：栈指针寄存器(extended stack pointer)，其内存放着一个指针，该指针永远指向系统栈最上面一个栈帧的栈顶 EBP：基址指针寄存器(extended base pointer)，其内存放着一个指针，该指针永远指向系统栈最上面一个栈帧的底部 函数栈帧：ESP和EBP之间的内存空间为当前栈帧，EBP标识了当前栈帧的底部，ESP标识了当前栈帧的顶部。

EIP：指令寄存器(extended instruction pointer)， 其内存放着一个指针，该指针永远指向下一条待执行的指令地址。

参数入栈：将参数从右向左依次压入系统栈中返回地址入栈：将当前代码区调用指令的下一条指令地址压入栈中，供函数返回时继续执行 代码区跳转：处理器从当前代码区跳转到被调用函数的入口处 栈帧调整：具体包括 保存当前栈帧状态值，已备后面恢复本栈帧时使用（EBP入栈） 将当前栈帧切换到新栈帧。（将ESP值装入EBP，更新栈帧底部） 给新栈帧分配空间。（把ESP减去所需空间的大小，抬高栈顶）

C语言： 函数调用之前的工作： （1）为被调用函数分配数据存储区； （2）将所有的实参、返回地址等信息传给被调用函数保存； （3）将控制转移到被调用函数的入口。 返回前的工作： （1）保存计算结果； （2）释放存储区； （3）控制转移。

26.递归函数优缺点

优点：简洁，在树的三种遍历方式中递归的实现要比非递归的实现简单。 缺点：效率较低，递归是有时间和空间消耗的，递归中很多计算都是重复的，从而给性能带来很大的负面影响。递归的本质是把一个问题分解为两个或多个小问题，这些小问题存在相互重叠的部分，因此也就存在重复的计算。递归也可能导致调用栈溢出，每一次函数调用都会在内存栈中分配空间，而每个进程的栈容量是有限的，如果函数调用的层级太多，就会超出栈的容量，从而导致栈溢出。

27.C和C++内存分配区别

在C/C++中，内存分为5个区：栈、堆、自由存储区（C++才有）、全局/静态存储区和常量存储区。

栈：就是那些由编译器在需要的时候分配，在不需要的时候自动清楚的变量的存储区，里面的变量通常是局部变量、函数参数等。

堆： 操作系统层面的术语。就是那些由malloc等分配的内存块，用free来结束自己的生命的。

自由存储区：C++层面上的术语，就是那些由new分配的内存块，他们的释放编译器不去管，由我们的应用程序去控制，一般一个new就要对应一个delete。如果程序员没有释放掉，那么在程序结束后，操作系统会自动回收。new的申请是调用的malloc，自由存储区就和堆类似，但不等价。存储对象可以在不立即初始化的情况下分配内存，并且可以在不立即释放内存的情况下销毁它们。

全局/静态存储区：全局变量和静态变量被分配到同一块内存中，在以前的C语言中，全局变量又分为初始化的和未初始化的，在C++里面没有这个区分了，他们共同占用同一块内存区。

常量存储区：这是一块比较特殊的存储区，他们里面存放的是常量，不允许修改，如字符串"abc"。

综合上述，C语言中全局变量会有初始化和未初始化的区分，C++没有。同样C++中有自由存储区的说法，而C语言没有

new与malloc的1