牛客高级系列专栏：

• 嵌入式面经专栏链接：嵌入式面经_C++软件开发面经_111道面试题全解析
• 嵌入式面经目录详情：111道嵌入式面经题全解析软件开发面经C++面经目录

• 嵌入式项目交流分享链接：嵌入式项目交流分享（附源码）

• 安卓高频面经专栏链接：Android面试题解析大全
• 安卓高频面经目录详情：安卓面经_Android面经_150道安卓基础面试题目录

• Android进阶知识体系解析专栏链接：Android进阶知识体系解析
• Android进阶知识体系解析目录详情：Android进阶知识体系解析_20大安卓进阶必备知识点

• 安卓系统Framework面经专栏链接：Android系统面试题解析大全
• 安卓系统Framework面经目录详情：Android系统面经_Framework开发面经_150道面试题答案解析

简介

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

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

正文开始⬇️

第四章 常见算法

4.1 排序算法 （本文讲 4.2.1-4.2.4)

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 STL库相关

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几种模板插入的时间复杂度 ⭐⭐⭐⭐⭐

4.2.1 vector list异同

解析：

1）数据结构的区别

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

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

2）迭代器支持不同

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

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

4.2.2 vector