算法设计与分析——递归与分治——归并排序

朱雀 2022-11-09 14:24 174阅读 0赞

归并排序采用的是一种分治的思想，如下图，先将要排序的元素分为两块，每个块又开始分裂，然后逐个按照特定顺序合并，合成最后我们需要的数组。  
归并排序的复杂度：  
时间复杂度：O(nlogn)  
空间复杂度：O(n)  
最好情况和最坏情况都是O(nlogn)  
是一种稳定的排序方法，因为在合并的同时保证了如果相同大小，左边的会先放进去

合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序，合并排序也叫归并排序。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]

函数：  
MergeSort()实现了归并排序  
Merge()函数 实现了将两个段合并到一起  
Copy()函数实现了将一个段复制到另一个段中去

#include<bits/stdc++.h>
    using namespace std;
    
    vector<int> vec;
    void copy(vector<int> &nums, vector<int> &vec, int left, int right);
    void Merge(vector<int> &nums, vector<int> &vec, int left, int mid, int right);
    
    void MergeSort(vector<int> &nums,int left,int right)
    {
        
        if(left<right)
        {
        
            int mid = (left + right) / 2;
            MergeSort(nums, left, mid);
            MergeSort(nums, mid + 1, right);
            Merge(nums, vec, left, mid, right);
            copy(nums, vec, left, right);
        }
        
    }
    
    void Merge(vector<int> &nums,vector<int> &vec,int left,int mid,int right)
    {
        
        int i=left, j=mid+1;
        while (i <= mid&&j <=right)
        {
        
            if(nums[i]<nums[j])
            {
        
                vec.push_back(nums[i]);
                i++;
            }
            else
            {
        
                vec.push_back(nums[j]);
                j++;
            }
            
        }
        while(i<=mid)
            {
        
                vec.push_back(nums[i]);
                i++;
            }
            while(j<=right)
            {
        
                vec.push_back(nums[j]);
                j++;
            }
    }
    
    void copy(vector<int> &nums,vector<int> &vec,int left,int right)
    {
        
      int i = left;
        int k = vec.size();
        for (int tempK = 0;((tempK < k)&&(i<=right));tempK++) {
        
    		nums[i] = vec[tempK];
    		i++;
    	}
        vec.clear();
    }
    
    
    
    int main()
    {
        
    
        vector<int> num1 = {
        5,4,6,3,1,2,8,7,10};
    	cout << "before sort " << endl;
    	for (auto a:num1) {
        
    		cout << a << "   ";
    	}
        MergeSort(num1, 0, 8);
        cout << endl << "after sort " << endl;
    	for (auto b:num1) {
        
    		cout << b<< "   ";
    	}
    	system("pause");
    	return 0;
    }

![在这里插入图片描述][20210602200513283.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221023/12c11061e72f47519b7dcbec87806d0a.png
[20210602200513283.png]: /images/20221023/ebdea677e8ec414a96e290bb984ad829.png