1. 说说什么是稳定的排序？⭐⭐⭐⭐⭐

  2. 说说动态规划算法⭐⭐⭐⭐⭐

  3. 手撕归并排序⭐⭐⭐⭐⭐

  4. 手撕快速排序⭐⭐⭐⭐⭐

  5. 手撕插入排序⭐⭐⭐⭐⭐

  6. 手撕堆排序⭐⭐⭐⭐⭐

  7. 手撕二分查找⭐⭐⭐⭐⭐

  8. 快排最差时间复杂度，堆排最差时间复杂度？⭐⭐⭐⭐⭐

  9. 说说各排序算法的时间复杂度？⭐⭐⭐⭐⭐

=========================================================================================================

  • 本专栏适合于C/C++已经入门的学生或人士，有一定的编程基础。
  • 本专栏适合于互联网C++软件开发、嵌入式软件求职的学生或人士。
  • 本专栏针对面试题答案进行了优化，尽量做到好记、言简意赅。这才是一份面试题总结的正确打开方式。这样才方便背诵
  • 针对于非科班同学，建议学习本人专刊文章《蒋豆芽的秋招打怪之旅》，该专刊文章对每一个知识点进行了详细解析。
  • 如专栏内容有错漏，欢迎在评论区指出或私聊我更改，一起学习，共同进步。
  • 相信大家都有着高尚的灵魂，请尊重我的知识产权，未经允许严禁各类机构和个人转载、传阅本专栏的内容。

=========================================================================================================

  1. 说说什么是稳定的排序？⭐⭐⭐⭐⭐

    • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
    • 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

    冒泡排序、归并排序是稳定排序；快速排序是不稳定排序。

  2. 说说动态规划算法⭐⭐⭐⭐⭐

    暴力解法有很多重复计算，动态规划就是为了帮助我们减少重复计算，所以动态规划提前存储前面计算的值，后面的值来源于已经存储的值，或者只需要在已经存储的值的基础上简单的叠加，这就是动态规划的本质，空间换时间。
    三个非常重要的领悟：
    1、动态规划应用于存在重复子结构的问题中，避免重复计算法
    2、动态规划空间换时间
    3、动态规划提前存储前面计算的值，后面的值来源于已经存储的值，或者只需要在已经存储的值的基础上简单的叠加

  3. 手撕归并排序⭐⭐⭐⭐⭐

    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)

  4. 手撕快速排序⭐⭐⭐⭐⭐

    //快排递归实现
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) {