算法与数据结构-3

C++软件与嵌入式软件面经解析大全（蒋豆芽的秋招打怪之旅）

本章讲解知识点

1.1 算法的时间复杂度和空间复杂度
1.2 数组
1.3 链表
1.4 递归
1.5 栈与队列
1.6 树与二叉树
1.7 二叉堆与最小堆
1.8 哈希表
1.9 红黑树
1.10 Trie（前缀树）
1.11 排序算法
1.12 查找算法
1.13 算法思想——DFS和BFS
1.14 算法思想——回溯
1.15 算法思想——分治法
1.16 算法思想——贪心法
1.17 算法思想——动态规划

受众：本教程适合于**C/C++**已经入门的学生或人士，有一定的编程基础。

本教程适合于互联网、嵌入式软件求职的学生或人士。

故事背景

**蒋豆芽：**小名豆芽，芳龄十八，蜀中人氏。卑微小硕一枚，科研领域苟延残喘，研究的是如何炒好一盘豆芽。与大多数人一样，学习道路永无止境，间歇性踌躇满志，持续性混吃等死。会点编程，对了，是面对对象的那种。不知不觉研二到找工作的时候了，同时还在忙论文，豆芽都秃了，不过豆芽也没头发啊。

**隔壁老李：**大名老李，蒋豆芽的好朋友，技术高手，代码女神。给了蒋豆芽不少的人生指导意见。

**导师：**蒋豆芽的老板，研究的课题是每天对豆芽嘘寒问暖。

故事引入

隔壁老李：刷题一段时间后，有什么感受？

蒋豆芽：数据结构实在是太重要了，数据结构是算法最根本的基础。

隔壁老李：是的，你说得没错，豆芽，你刷了这么久的题，有什么算法总结吗？

蒋豆芽：当然有！今天我就来班门弄斧一下吧！

1.11 排序算法

蒋豆芽：我这里就直接总结了：

冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地遍历要排序的数组，一次比较两个元素，如果它们的顺序错误就把它们交换过来。直到数组排序完成。

算法描述
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。

代码如下：

class Solution {
    void bubbleSort(vector<int>& nums){
       for (int i=0; i<nums.size(); i++){
           for (int j=0; j<nums.size()-i-1; j++){
               if (nums[j] > nums[j+1])
                    swap(nums[j], nums[j+1]); // 交换两元素
           }
       }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        if (nums.empty()) return {};
        bubbleSort(nums);
        return nums;
    }
};
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)

选择排序（Selection Sort）

选择排序（Selection-sort）简单直观。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述

假设n个待排序数据。具体算法描述如下：
- 初始状态：无序区为R[1..n]，有序区为空；
- 第i趟排序（i=1,2,3…n-1）开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小（或最大）的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- n-1趟结束，数组有序化了。

代码如下：

class Solution {
    void selectSort(vector<int> &arr){
        int N = arr.size();
        for (int i=0; i<N-1; i++){
            int min = i;
            for (int j=i+1; j<N; j++){ // 每一轮在无序区找到最小值
                if (arr[j] < arr[min])
                    min = j;
            }
            swap(arr[i], arr[min]); // 最小值与无序区第一个元素交换
        }    
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        selectSort(nums);
        return nums;
    }
};
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)

插入排序（Insertion Sort）

插入排序（Insertion-Sort）简单直观。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。

代码如下：

class Solution {
    void straightSort(vector<int> &arr){
        int N = arr.size();
        for (int i=1; i<N; i++){
            for (int j=i-1; j>=0&&arr[j+1]<arr[j]; j-=1){
                swap(arr[j+1], arr[j]);
            }
        }    
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        straightSort(nums);
        return nums;
    }
};
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)

希尔排序（Shell Sort）

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k 趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

class Solution {
    void shellSort(vector<int> &arr){
        int N = arr.size();
        //进行分组，最开始的增量gap为数组长度的一半
        for (int gap=N/2; gap>0; gap/=2){
            for (int i=gap; i<N; i++){
                for (int j=i-gap; j>=0&&arr[j+gap]<arr[j]; j-=gap){ // 这里是插入排序
                    swap(arr[j+gap], arr[j]);
                }
            }
        }    
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        shellSort(nums);
        return nums;
    }
};
// 时间复杂度：位于O(nlogn)和O(n^2)之间
// 空间复杂度：O(1)

归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。

代码如下：

class Solution {
    void mergeSort(vector<int>& nums, vector<int>& temp, int l, int r){
        if (l >= r) return;
        int mid = (l + r) / 2;
        mergeSort(nums, temp, l, mid);     // 这里拆分下去，变成一个个的子序列
        mergeSort(nums, temp, mid+1, r);
        int i=l,j=mid+1; int t = 0;        // 针对左右子序列，使用归并方法合并成一个有序数列
        while (i<=mid && j<=r){
            if (nums[i] <= nums[j]) temp[t++] = nums[i++];
            else temp[t++] = nums[j++];
        }
        while (i <= mid) temp[t++] = nums[i++];
        while (j <= r) temp[t++] = nums[j++];
        
        for (int i=l,t=0; i<=r; i++)
            nums[i] = temp[t++];
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        if (nums.empty()) return {};
        vector<int> temp(nums.size(), 0);
        mergeSort(nums, temp, 0, nums.size()-1);
        return nums;
    }
};
// 时间复杂度：O(nlogn)
// 空间复杂度：O(n)

快速排序（Quick Sort）

快速排序的基本思想：也是采用分治的思想，将数组拆分成一个个的子序列，针对每个子序列进行排序，排序的方法是，设立一个“基准元素”，比“基准元素”小的数字放左边，比“基准元素”大的数字放右边。

算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码如下：

//快排递归实现
class Solution {
    void quickSort(vector<int>& nums, int l, int r){
        if (l >= r) return;
        int mark = nums[l];        // 设置“基准元素”
        int mark_ptr = l;
        for (int i=l; i<=r; i++){
            if (nums[i] < mark){
                mark_ptr++;
                swap(nums[i], nums[mark_ptr]);
            }
        }
        swap(nums[mark_ptr], nums[l]);
        quickSort(nums, l, mark_ptr-1);
        quickSort(nums, mark_ptr+1, r);
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        if (nums.empty()) return {};
        quickSort(nums, 0, nums.size()-1);
        return nums;
    }
};
// 时间复杂度：O(nlogn)
// 空间复杂度：O(logn)

//快排非递归实现，利用栈，BFS的思想，存储前后指针
class Solution {
    void quickSort(vector<int>& nums, int l, int r){
        using Pair = pair<int,int>;
        stack<Pair> stk; stk.push(Pair(l, r));
        while (!stk.empty()){
            auto index = stk.top(); stk.pop();
            int l = index.first; int r = index.second;
            if (l >= r) continue;
            int mark = nums[l];
            int mark_ptr = l;
            for (int i=l; i<=r; i++){
                if (nums[i] < mark){
                    mark_ptr++;
                    swap(nums[i], nums[mark_ptr]);
                }
            }
            swap(nums[mark_ptr], nums[l]);
            stk.push(Pair(l, mark_ptr-1));
            stk.push(Pair(mark_ptr+1, r));
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        if (nums.empty()) return {};
        quickSort(nums, 0, nums.size()-1);
        return nums;
    }
};
// 时间复杂度：O(nlogn)
// 空间复杂度：O(n)

堆排序（Heap Sort）

堆排序（Heapsort）是指利用二叉堆这种数据结构所设计的一种排序算法。二叉堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法描述
- 将初始待排序关键字数列（R1,R2….Rn）构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

我们看下代码：

class Solution {
    void heap(vector<int>& nums, int p){ // 调整堆
       for (int parent=p; parent*2+1<nums.size();){
           int child = parent*2+1;
           if (child+1<nums.size() && nums[child] > nums[child+1])
                child++;
            if (nums[child] > nums[parent])
                break;
            swap(nums[child], nums[parent]);
            parent = child;
       }
    }
    void buildheap(vector<int>& nums){ // 建堆
        for (int i=nums.size()/2; i>=0; i--)
            heap(nums, i);
    }
public:

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

校招面试考点全解析——C++软件与嵌入式篇(蒋豆芽的秋招打怪之旅) 文章被收录于专栏

- 本专刊适合于C/C++已经入门的学生或人士，有一定的编程基础。 - 本专刊适合于互联网C++软件开发、嵌入式软件求职的学生或人士。 - 本专刊囊括了C语言、C++、操作系统、计算机网络、嵌入式、算法与数据结构等一系列知识点的讲解，并且最后总结出了高频面试考点（附有答案）共近400道，知识点讲解全面。不仅如此，教程还讲解了简历制作、笔试面试准备、面试技巧等内容。