牛客高级系列专栏：

• 嵌入式面经专栏链接：嵌入式面经_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.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.1 排序算法

4.1.1各种排序算法的时间空间复杂度、稳定性（这个表格很重要，一定要记清楚）

问：什么是稳定性？

答：排序算法稳定性的简单形式化定义为：如果Ai = Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。通俗地讲就