简介

本人2020年本硕毕业于广东工业大学：嵌入式许乔丹，牛客高级专栏作者，牛客大学讲师，本科阶段搞了4年单片机、曾参加全国大学生恩智浦汽车竞赛，发表4个硬件专利。研究生阶段找了嵌入式linux的实习，毕业后拿到珠海格力，云从科技，CVTE，小米，美的，华为的嵌入式offer，签约CVTE嵌入式岗位。

在CVTE先后做过嵌入式Linux开发和安卓系统开发，参与过TV板卡、显示屏板卡、智能家居板卡、希沃网课学习机的开发。欢迎交流嵌入式或者安卓哈！

正文开始⬇️

4.1.1各种排序算法的时间空间复杂度、稳定性⭐⭐⭐⭐⭐

4.1.2各种排序算法什么时候有最好情况、最坏情况（尤其是快排） ⭐⭐⭐⭐

4.1.3冒泡排序⭐⭐⭐⭐

4.1.4选择排序⭐⭐⭐⭐

4.1.5插入排序⭐⭐⭐⭐

4.1.6希尔排序⭐⭐⭐⭐

4.1.7归并排序⭐⭐⭐⭐

4.1.8快速排序⭐⭐⭐⭐⭐

4.1.9快排的partition函数与归并的Merge函数⭐⭐⭐

4.2.1 vector list异同⭐⭐⭐⭐⭐

4.2.2 vector内存是怎么增长的vector的底层实现⭐⭐⭐⭐

4.2.3 vector和deque的比较⭐⭐⭐⭐

4.2.4为什么stl里面有sort函数list里面还要再定义一个sort⭐⭐⭐

4.2.5 STL底层数据结构实现⭐⭐⭐⭐

4.2.6利用迭代器删除元素会发生什么？⭐⭐⭐⭐

4.2.7 map是如何实现的，查找效率是多少⭐⭐⭐⭐⭐

4.2.8几种模板插入的时间复杂度 ⭐⭐⭐⭐⭐

解析：

1）数据结构的区别

vector与数组类似，拥有一段连续的内存空间，并且起始地址不变。便于随机访问，时间复杂度为O（1），但因为内存空间是连续的，所以在进入插入和删除操作时，会造成内存块的拷贝，时间复杂度为O（n）。此外，当数组内存空间不足，会采取扩容，通过重新申请一块更大的内存空间进行内存拷贝。

list底层是由双向链表实现的，因此内存空间不是连续的。根据链表的实现原理，List查询效率较低，时间复杂度为O（n），但插入和删除效率较高。只需要在插入的地方更改指针的指向即可，不用移动数据。

2）迭代器支持不同

异：vector中，iterator支持”+“、”+=“，”<"等操作。而list中则不支持。

同：vector<int>::iterator和list<int>::iterator都重载了“++ ”操作。