牛客高级系列专栏：

简介

本人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, start, mid, end, temp);
}

int main()
{    
    int a[8] = { 6, 5, 3, 1