1. 排序算法简单介绍（快速排序，插入排序，冒泡排序）

冒泡排序（C++实现）_m0_37548423的博客-CSDN博客_冒泡排序c++

//bubble：
for(int i=0;i<len;i++)
{
    for(int j=1;j<len-i;j++)
    {
        if(nums[j-1]>nums[j]) swap(nums[j-1],nums[j]);
    }
}

2. 数组和链表的区别

1.从逻辑结构上来看： 数组必须实现定于固定的长度，不能适应数据动态增减的情况，即数组的大小一旦定义就不能改变。当数据增加时，可能超过原先定义的元素的个数；当数据减少时，造成内存浪费；链表动态进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。

2.从内存存储的角度看； 数组从栈中分配空间（用new则在堆上创建），对程序员方便快速，但是自由度小；链表从堆中分配空间，自由度大但是申请管理比较麻烦。

3. 从访问方式类看: 数组在内存中是连续的存储，因此可以利用下标索引进行访问；链表是链式存储结构，在访问元素时候只能够通过线性方式由前到后顺序的访问，所以访问效率比数组要低。

3. 红黑树的了解（平衡树，二叉搜索树），使用场景

1.AVLtree 定义：最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。 一般我们所看见的都是排序平衡二叉树。

AVLtree使用场景：AVL树适合用于插入删除次数比较少，但查找多的情况。插入删除导致很多的旋转，旋转是非常耗时的。AVL 在linux内核的vm area中使用。

2.二叉搜索树 二叉搜索树也是一种树，适用与一般二叉树的全部操作，但二叉搜索树能够实现数据的快速查找。

二叉搜索树满足的条件：

1. 非空左子树的所有键值小于其根节点的键值
2. 非空右子树的所有键值大于其根节点的键值
3. 左右子树都是二叉搜索树 　　 二叉搜索树的应用场景：如果是没有退化称为链表的二叉树，查找效率就是lgn，效率不错，但是一旦退换称为链表了，要么使用平衡二叉树，或者之后的RB树，因为链表就是线性的查找效率。

3.红黑树的定义 红黑树是一种二叉查找树，但在每个结点上增加了一个存储位表示结点的颜色，可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

当二叉查找树的高度较低时，这些操作执行的比较快，但是当树的高度较高时，这些操作的性能可能不比用链表好。红黑树（red-black tree）是一种平衡的二叉查找树，它能保证在最坏情况下，基本的动态操作集合运行时间为O(lgn)。

红黑树必须要满足的五条性质：

性质一：节点是红色或者是黑色； 在树里面的节点不是红色的就是黑色的，没有其他颜色，要不怎么叫红黑树呢，是吧。 性质二：根节点是黑色； 根节点总是黑色的。它不能为红。 性质三：每个叶节点（NIL或空节点）是黑色； 性质四：每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点）； 就是连续的两个节点不能是连续的红色，连续的两个节点的意思就是父节点与子节点不能是连续的红色。 性质五：从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点。从根节点到每一个NIL节点的路径中，都包含了相同数量的黑色节点。

红黑树的应用场景：红黑树是一种不是非常严格的平衡二叉树，没有AVLtree那么严格的平衡要求，所以它的平均查找，增添删除效率都还不错。广泛用在C++的STL中。如map和set都是用红黑树实现的。

4.B树定义

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），不属于二叉搜索树的范畴，因为它不止两路，存在多路。

B树满足的条件：

（1）树种的每个节点最多拥有m个子节点且m>=2,空树除外（注：m阶代表一个树节点最多有多少个查找路径，m阶=m路,当m=2则是2叉树,m=3则是3叉）； （2）除根节点外每个节点的关键字数量大于等于ceil(m/2)-1个小于等于m-1个，非根节点关键字数必须>=2;（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2) （3）所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子 （4）如果一个非叶节点有N个子节点，则该节点的关键字数等于N-1; （5）所有节点关键字是按递增次序排列，并遵循左小右大原则；

B树的应用场景：构造一个多阶的B类树，然后在尽量多的在结点上存储相关的信息，保证层数尽量的少，以便后面我们可以更快的找到信息，磁盘的I/O操作也少一些，而且B类树是平衡树，每个结点到叶子结点的高度都是相同，这也保证了每个查询是稳定的。

5.B+树 B+树是B树的一个升级版，B+树是B树的变种树，有n棵子树的节点中含有n个关键字，每个关键字不保存数据，只用来索引，数据都保存在叶子节点。是为文件系统而生的。

特点：相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。在B树的基础上每个节点存储的关键字数更多，树的层级更少所以查询数据更快，所有指关键字指针都存在叶子节点，所以每次查找的次数都相同所以查询速度更稳定。 应用场景： 用在磁盘文件组织 数据索引和数据库索引。

6.为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别 B树和B+树的区别，以一个m阶树为例。

1. 关键字的数量不同；B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用，但是B树虽然也有m个子结点，但是其只拥有m-1个关键字。
2. 存储的位置不同；B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。
3. 分支结点的构造不同；B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。
4. 查询不同；B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。 参考资料：常见题目 - holmes_now - 博客园 (cnblogs.com)

5.排序算法有哪些？< C语言总共有多少种排序法>

下面列一些常见的算法：插入排序，冒泡排序，选择排序，快速排序，堆排序，归并排序，基数排序，希尔排序等。

6.怎么理解哈希表,哈希表是什么

散列表（Hash table，也叫哈希表），是根据关键码值(Key value) 而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。 这个映射函数叫做散列函数，存放记录的数组叫做散列表。 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数

7.简述快速排序过程

1）选择一个基准元素,通常选择第一个元素或者最后一个元素, 2）通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。 3）此时基准元素在其排好序后的正确位置 4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

8.各类排序算法的比较

1. 说明： 当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）； 而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）； 原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

2.稳定性： 排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。  稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

9.KMP算法：

在一个字符串中查找是否包含目标的匹配字符串。其主要思想是每趟比较过程让子串先后滑动一个合适的位置。当发生不匹配的情况时，不是右移一位，而是移动（当前匹配的长度– 当前匹配子串的部分匹配值）位。

10.vector底层实现和扩容机制

底层实现： STL 众多容器中，vector 是最常用的容器之一，其底层所采用的数据结构非常简单，就只是一段连续的线性内存空间。 通过分析 vector 容器的源代码不难发现，它就是使用 3 个迭代器（可以理解成指针）来表示的：

//_Alloc 表示内存分配器，此参数几乎不需要我们关心
template <class _Ty, class _Alloc = allocator<_Ty>>
class vector{
    ...
protected:
    pointer _Myfirst;
    pointer _Mylast;
    pointer _Myend;
};

其中，_Myfirst 指向的是 vector 容器对象的起始字节位置；_Mylast 指向当前最后一个元素的末尾字节；_myend 指向整个 vector 容器所占用内存空间的末尾字节。

vector扩大容量的本质 另外需要指明的是，当 vector 的大小和容量相等（size==capacity）也就是满载时，如果再向其添加元素，那么 vector 就需要扩容。vector 容器扩容的过程需要经历以下 3 步： 1.完全弃用现有的内存空间，重新申请更大的内存空间； 2.将旧内存空间中的数据，按原有顺序移动到新的内存空间中； 3.最后将旧的内存空间释放

11.迭代器什么时候失效

vector迭代器什么时候会失效？ 一、 push_back导致迭代器失效 vector在push_back的时候当容量不足时会触发扩容，导致整个vector重新申请内存，并且将原有的数据复制到新的内存中，并将原有内存释放，这自然是会导致迭代器失效的，因为迭代器所指的内存都已经被释放。

二、insert导致迭代器失效 insert导致的迭代器失效有两种情况： （1）插入操作导致vector扩容，迭代器失效原因和push_back相同 （2）插入操作引起vector内元素移动，导致被移动部分的迭代器失效

三、erase导致迭代器失效 删除操作引起vector内元素移动，导致被移动部分的迭代器失效。

关联性容器迭代器何时失效？ 对于关联容器(如map, set,multimap,multiset)，删除当前的iterator，仅仅会使当前的iterator失效，只要在erase时，递增当前iterator即可。这是因为map之类的容器，使用了红黑树来实现，插入、删除一个结点不会对其他结点造成影响。erase迭代器只是被删元素的迭代器失效，但是返回值为void，所以要采用erase(iter++)的方式删除迭代器。

链表式容器迭代器何时失效？ 对于链表式容器(如list)，删除当前的iterator，仅仅会使当前的iterator失效，这是因为list之类的容器，使用了链表来实现，插入、删除一个结点不会对其他结点造成影响。只要在erase时，递增当前iterator即可，并且erase方法可以返回下一个有效的iterator。

四、总结

迭代器失效分三种情况考虑，也是分三种数据结构考虑，分别为数组型，链表型，树型数据结构。

数组型数据结构：（vector）该数据结构的元素是分配在连续的内存中，insert和erase操作，都会使得删除点和插入点之后的元素挪位置，所以，插入点和删除掉之后的迭代器全部失效，也就是说insert(*iter)(或erase(*iter))，然后在iter++，是没有意义的。 解决方法：erase(*iter)的返回值是下一个有效迭代器的值。 iter =cont.erase(iter);

链表型数据结构：（list）对于list型的数据结构，使用了不连续分配的内存，删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器. 解决办法两种，erase(*iter)会返回下一个有效迭代器的值，或者erase(iter++).

树形数据结构： (map,set)使用红黑树来存储数据，插入不会使得任何迭代器失效；删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器. erase迭代器只是被删元素的迭代器失效，但是返回值为void，所以要采用erase(iter++)的方式删除迭代器。

注意：经过erase(iter)之后的迭代器完全失效，该迭代器iter不能参与任何运算，包括iter++,*iter

12.STL介绍

1.STL六大组件？

容器，迭代器，算法，仿函数，空间配置器，容器配接器。

容器：各种数据结构，如vector、list、deque、set、map等,用来存放数据，从实现角度来看，STL容器是一种class template。、

算法：各种常用的算法，如sort、find、copy、for_each。从实现的角度来看，STL算法是一种function tempalte.

迭代器：扮演了容器与算法之间的胶合剂，共有五种类型，从实现角度来看，迭代器是一种将operator* , operator-> , operator++,operator–等指针相关操作予以重载的class template. 所有STL容器都附带有自己专属的迭代器，只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。

仿函数：行为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是一种重载了operator()的class 或者class template

适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。

空间配置器：负责空间的配置与管理。从实现角度看，配置器是一个实现了动态空间配置、空间管理、空间释放的class tempalte.

2.简单介绍vector？ vector 动态数组，支持随机访问，但是插入删除效率低，因为内存连续分配，插入删除将可能使迭代器失效。当分配的内存空间不足时，开辟之前的内存空间的若干倍（通常是2倍或1.5倍），将原先内存中的数据拷贝移动到新开辟的内存空间中。

3.简单介绍list？ list 双向链表，内存不连续分配，故不支持随机访问，插入删除效率高，但是查找效率低。

4.简单介绍deque？ deque 双端队列，支持随机访问，底层存储机制较为复杂，由若干连续小段空间通过指针连接而成，由中央控制器map（不是容器的map）统一管理。由于特殊存储机制，迭代器的实现较为复杂，故效率略低。

5.简单介绍map？ map/multiset 映射，关联容器。每个键映射一个值，底层数据结构由红黑树实现，每次插入删除只会影响当前节点的内存分配（开辟/释放），所以map的插入删除效率比用其他序列容器高。但是由于内部存储的已经不是元素本身（例如还要存子节点地址，父亲节点地址，节点颜色等），导致不能像vector一样预分配内存空间。Set同理。

6.map与multimap的区别？ multimap同map的区别就是multiset键可以重复而map键不能重复。

7.简单介绍红黑树？ 红黑树虽然相比AVL树要求两颗子树的高度差的绝对值小于等于1的严格平衡二叉树来说没有那么严格，但是仍然可以保证根节点出发的简单路径中最长的那条路径长度小于等于最短的那条的两倍。 这是由其性质决定： 1.节点颜色由红色和黑色组成 2.根节点必须为黑色 3.叶子节点全为黑色并且是null节点 4.红色节点的儿子不能是红色 5.任意一个节点到叶子节点的所有简单路径中黑色节点的个数相同。 具体每次插入和删除通过旋转和变色来维护这些性质，由于每次旋转次数稳定，故性能较AVL树好。

8.简单介绍set/multiset？ set/multiset 集合，关联容器。值就是键，底层也由红黑树实现。multiset的键可以重复而set不能。

9.简单介绍Unorder_map/unordered_set？ Unordered_map由哈希桶实现，利用链地址法解决冲突。内部没有按照键或值的任何顺序进行排序，而实根据散列值组织成桶允许通过键直接访问单个元素，均摊时间复杂度为常数级别。unorder_set除了值就是键以外和unordered_map大体相同。

10.SGI Stl的内存分配方式? SGI设计了两层的配置器，也就是第一级配置器和第二级配置器，默认使用第二级配置器。第一级配置器直接调用malloc和free来分配释放内存。第二级配置器：根据情况来判定，如果用户需要的区块大于128，则直接调用第一级配置器；如果用户需要的区块小于128，则到自由链表中去查找。若自由链表中对应位置没有内存块，那么就向内存池中申请内存块。

11.为什么需要优化和内存池等细节？ 1）频繁使用malloc、free开辟释放小块内存带来的性能效率低下。 2）内存碎片，导致不连续的内存不可用的资源浪费。\

12.为什么vector的插入操作可能会导致迭代器失效？ vector动态增加大小时，并不是在原空间后增加新的空间，而是以原大小的两倍在另外配置一片较大的新空间，然后将内容拷贝过来，并释放原来的空间。由于操作改变了空间，所以迭代器失效。

13.不允许有遍历行为的容器有哪些（不提供迭代器）？ 1）queue，除了头部外，没有其他方法存取deque的其他元素。 2）stack（底层以deque实现），除了最顶端外，没有任何其他方法可以存取stack的其他元素。 3）heap，所有元素都必须遵循特别的排序规则，不提供遍历功能。

14.STL容器的参数allocate是用来做什么的？ 分配器用于封装STL容器在内存管理上的低层细节。

15.vector中erase方法与algorithm中的remove方法区别？以及size()和capacity()的区别？ vector中erase方法真正删除了元素，迭代器不能访问了。 而remove()是STL中的一个算法，对一个容器调用remove并不会改变容器中的元素个数。remove只是简单地将元素移到了容器的最后面，并不会真正的删除该元素，迭代器还是可以访问到。 因为algorithm通过迭代器进行操作，不知道容器的内部结构，所以无法进行真正的删除。 Size()返回当前容器拥有的元素个数。而capacity返回在容器扩容之前可以存储的元素个数。

16.为何map和set的插入删除效率比其他序列容器高？ 因为不需要内存的移动和拷贝。

17.为何map和set每次Insert之后，以前保存的iterator不会失效？ 因为每次插入删除会动态开辟释放内存空间，只有当前变化的节点iterator失效，之前保存的iterator由于内存空间未发生变化所以并不会失效。

18.map能不能边遍历边删除？ 不可以，因为map删除了一个元素之后该元素对应节点的迭代器失效，且erase并不返回下一个元素的迭代器。

13.数据库索引为什么用B+树

原因如下:

1. B+树能显著减少IO次数，提高效率
2. B+树的查询效率更加稳定，因为数据放在叶子节点
3. B+树能提高范围查询的效率，因为叶子节点指向下一个叶子节点 索引如何优化：

慢查询日志、查磁盘的I/O读写的数据量、show status

MySQL可以设置慢查询日志，当SQL执行的时间超过我们设定的时间，那么这些SQL就会被记录在慢查询日志当中，然后我们通过查看日志，用explain分析这些SQL的执行计划，来判定为什么效率低下，是没有使用到索引？还是索引本身创建的有问题？或者是索引使用到了，但是由于表的数据量太大，花费的时间就是很长，那么此时我们可以把表分成n个小表，比如订单表按年份分成多个小表等。 数据库毕竟是磁盘存储，我们可以通过项目运行过程中，检测磁盘I/O读写的数据量，来定位效率低下的SQL。

MySQL提供了show status命令，查看MySQL Server的运行参数，可以查看select，insert，delete，update语句的执行频率，慢查询次数，事务的提交和回滚的次数