蒋豆芽的面试题专栏（30/数据结构与算法）

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]);
           q