422-分治算法-归并排序

绝地灬酷狼 2022-09-05 04:05 199阅读 0赞

## 分治算法-归并排序 ##

![在这里插入图片描述][d75c109a15d04a919e5595e0debff529.png]  
**对上面数据进行归并排序**

**我们进行划分**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
**回溯的时候，一层一层处理，进行合并成有序的序列。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
**空间复杂度：有多少元素，就要额外开辟多少的数组空间！**  
**最好，最坏，平均的时间复杂度：**  
![在这里插入图片描述][a5d1faff82494843b3f77d86052bc4c6.png]

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    void merge(vector<int>& vec, int low, int high, int mid)
    {
        
    	//定义额外的辅助空间，存储合并的子问题的有序数组
    	vector<int> tmp;
    	tmp.reserve(high - low + 1);//reserve resize
    	int i = low;//[low, mid]
    	int j = mid + 1;//[mid+1, high]
    
    	while (i <= mid && j <= high)
    	{
        
    		if (vec[i] > vec[j])
    		{
        
    			tmp.push_back(vec[j++]);
    		}
    		else
    		{
        
    			tmp.push_back(vec[i++]);
    		}
    	}
    
    	while (i <= mid)
    	{
        
    		tmp.push_back(vec[i++]);
    	}
    
    	while (j <= high)
    	{
        
    		tmp.push_back(vec[j++]);
    	}
    
    	//tmp里面的元素 =》 数组vec当中
    	for (int k = low; k <= high; ++k)
    	{
        
    		vec[k] = tmp[k - low];
    	}
    }
    //分治算法应用 - 归并排序
    void mergeSort(vector<int>& vec, int i, int j)
    {
        
    	if (i >= j)
    	{
         //子问题划分到一个元素的时候，就代表子问题的解是已知的了
    		return;
    	}
    	int mid = (i + j) / 2;
    	//先划分子问题，降低问题规模
    	mergeSort(vec, i, mid);
    	mergeSort(vec, mid + 1, j);
    
    	//向上回溯，回溯的过程中，合并子问题的解
    	merge(vec, i, j, mid);//[i,mid] [mid+i, j]
    }
    int main()
    {
        
    	vector<int> vec;
    	for (int i = 0; i < 11; ++i)
    	{
        
    		vec.push_back(rand() % 100);
    	}
    
    	for (int v : vec)
    	{
        
    		cout << v << " ";
    	}
    	cout << endl;
    
    	mergeSort(vec, 0, vec.size() - 1);
    	for (int v : vec)
    	{
        
    		cout << v << " ";
    	}
    	cout << endl;
    
    	return 0;
    }

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

[d75c109a15d04a919e5595e0debff529.png]: /images/20220829/7780d208eba84c78bb080baca9be548f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/ee9644ba1fc64368b9302826874bfbf6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/07d66aefa1d345a0b6cea3bf26390237.png
[a5d1faff82494843b3f77d86052bc4c6.png]: /images/20220829/a3cc3b74bd034984bbff61db8f38d8b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/b36a307e287647bf80996456c01a38fa.png