牛客高级系列专栏：

• 嵌入式面经专栏链接：嵌入式面经_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.1.10循环队列的实现⭐⭐⭐

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.7归并排序(Merge Sort)

void Merge(int arr[], int start, int mid, int end, int * temp)
{
    //合并两个有序序列    
    int length = 0;
    //表示辅助空间有多少个元素    
    int i_start = start;    
    int i_end = mid;    
    int j_start = mid + 1;    
    int j_end = end;    
    while (i_start <= i_end && j_start <= j_end)
    {        
        if (arr[i_start] < arr[j_start])
        {            
            temp[length] = arr[i_start];             
            length++;            
            i_start++;        
        }        
        else        
        {            
            temp[length] = arr[j_start];            
            length++;            
            j_start++;        
        }    
    }    
    while (i_start <= i_end)    
    {        
        temp[length] = arr[i_start];        
        i_start++;        
        length++;    
    }    

    while (j_start <= j_end)    
    {        
        temp[length] = arr[j_start];        
        length++;        
        j_start++;    
    }    

    //把辅助空间的数据放到原空间    
    for (int i = 0; i < length; i++)    
    {        
        arr[start + i] = temp[i];    
    }
}

void MergeSort(int arr[], int start, int end, int * temp)
{    
    if (start >= end)
        return;    
    int mid = (start + end) / 2;    
    MergeSort(arr, start, mid, temp);
    MergeSort(arr, mid + 1, end, temp);     
    Merge(arr,