每日一题--归并排序

╰+攻爆jí腚メ 2023-02-26 07:28 39阅读 0赞

### 每日一题--归并排序 ###

今天带来的是归并排序，与快排和堆排相比，归并排序的使用场景就没有那么高了，面试中一般也很少遇到，不过它的排序思想还是很有意思的，主要是分拆和合并。理解了归并排序的思想，对一些其他的算法场景很有启发价值。  
**思路**  
　　归并排序主要分为两步：分拆和合并。分拆就是把一个长序列分成若干个短序列，合并就是把两个有序的序列合并成一个有序的长序列。具体到归并排序来说，首先需要将数组分拆到只有一个元素的小序列，在这个过程中可以使用递归。分拆完成后，再把每个小序列两两合并，最终合并成为一个有序的长序列，即完成排序过程。在合并过程中，我们需要申请一个临时数组来保存两个待合并序列排序后的元素，等待合并完成后，再将该临时数组中的元素拷贝回原数组。  
**代码实现**

void merge(int* v, int start, int mid, int end){
        
      int size = end - start + 1;
      int* temp = new int[size];
      int i = start, j = mid + 1;
      int len = 0;
      while(i <= mid && j <= end){
        
        if(v[i] < v[j]){
        
          temp[len++] = v[i++];
        }
        else{
        
          temp[len++] = v[j++];
        }
      }
      while(i <= mid){
        
        temp[len++] = v[i++];
      }
      while(j <= end){
        
        temp[len++] = v[j++];
      }
      for(k = 0; k < len; k++){
        
        v[start + k] = temp[k];
      }
      delete[] temp;
    }
    
    void sort(int* v, int start, int end){
        
      if(start > end){
        
        return;
      }
      int mid = (start + end) / 2;
      sort(v, start, mid);
      sort(v, mid + 1, end);
      merge(v, start, mid, end);
    }

今天学习了归并排序，主要是它先分拆再合并的思想很有意思。各位小伙伴如有兴趣，可以扫扫下面的二维码加入每日一题的大本营，每天发一道算法题和题解，期待与各位交流~  
　　![在这里插入图片描述][20200714193152222.jpg]

[20200714193152222.jpg]: /images/20230209/9ae4603440f54070954e0d6abfc670f0.png