583-归并排序算法的思想和性能分析

短命女 2022-09-12 01:46 160阅读 0赞

## 归并排序算法的思想![在这里插入图片描述][a41dc0055ba44504ba9bf1c8684bfaec.png] ##

**归并排序算法不仅仅可以做内排序(内存上的排序)，还可以做外排序(磁盘上文件的数据的排序)**

**归并排序算法**：**归就是递归的归**，递的过程是缩减数据规模到头，规模小到结果是已知的，然后归的过程是在计算各个规模的结果，累计出原始数据规模的结果。  
![在这里插入图片描述][4e878e1cba164b57ac189a61074ddd20.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][de9260ab509440c98ffce4b476cb5a7b.png]

**我们看下面这一行待排序的序列**  
![在这里插入图片描述][22074c9dba864f49aed7d8ea4323663e.png]  
**要归并，首先要先递，递的过程是在缩小数据规模，对于数组来说，缩小数据规模就是缩小起始和末尾下标的数据的长度，递到序列里只剩下1个元素为头。**  
序列中起始下标是0，末尾下标是9  
![在这里插入图片描述][e6a851875d9a4d4097b9933e08319126.png]  
**首先，进行递**  
把原始序列进行分段  
**我们采用的是二路归并！都是在原数组上操作的，没有开辟额外的空间。**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

**继续划分**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
**继续划分**  
序列中只有1个元素，就认为是已经有序的，  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
**继续划分**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
**以上这就是归并排序的递的过程，已经递到头了，元素的左右下标已经是相等了，1个序列只有1个元素，所以每个序列已经是有序了，这就是递归结束的条件**

**现在要进行归并排序的归并了**  
相当于是在二叉树中从叶子节点往根节点回退的过程  
**我们需要申请额外的空间了**  
因为对于底层的62序列和99序列，我们认为是已经有序的了，它们两个在归的过程中要往父节点归，归的过程中就要把这2个分别有序的序列合并成1个全局有序的序列。  
我们定义i,j分别指向这2个序列的起始  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16]  
比谁小，先放谁到这个开辟的空间上  
62小于99，然后把62放入空间中，然后i++，这个序列只有1个元素，所以结束了  
现在j这个序列有1个元素99，然后把99放到空间中  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]  
然后把这个空间中合并的全局的有序序列的结果返回父节点，对应的0-1号的数组位置中。  
**然后继续向上归**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_13_color_FFFFFF_t_70_g_se_x_16]  
把序列：62 99和序列：38合并成1个全局的有序序列  
同样的，给这两个序列分别定义i和j指向起始，然后开辟额外的空间  
i和j比较，谁小，谁先放，j指向的元素小，j先放进去空间中，然后j++，  
j越界了，然后把i的序列中的值按顺序放进去。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16 1]

然后拷贝到0-2号元素的内存空间中  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_13_color_FFFFFF_t_70_g_se_x_16 1]  
**以此类推下去。**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
**然后就是回退到根节点，合并成最终的整个有序结果：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
![在这里插入图片描述][59d93bbe744b4c65acb5e199bcbfeb84.png]

## 归并排序算法的代码实现 ##

#include <iostream>
    using namespace std;
    
    //归并过程函数  O(n)
    void Merge(int arr[], int l, int m, int r, int* p)
    {
        
    	int idx = 0;
    	int i = l;
    	int j = m + 1;
    
    	while (i <= m && j <= r)//较小的那个值先放进开辟的数组中 
    	{
        
    		if (arr[i] <= arr[j])
    		{
        
    			p[idx++] = arr[i++];
    		}
    		else
    		{
        
    			p[idx++] = arr[j++];
    		}
    	}
    
    	while (i <= m)//i这个序列有剩余元素 
    	{
        
    		p[idx++] = arr[i++];
    	}
    
    	while (j <= r)//j这个序列有剩余元素 
    	{
        
    		p[idx++] = arr[j++];
    	}
    
    	//再把合并好的大段有序的结果，拷贝到原始arr数组[l,r]区间内
    	for (i = l, j = 0; i <= r; i++, j++)
    	{
        
    		arr[i] = p[j];
    	}
    }
    
    //归并排序递归接口
    void MergeSort(int arr[], int begin, int end, int* p)
    {
        
    	//递归结束的条件
    	if (begin >= end)
    	{
        
    		return;
    	}
    
    	int mid = (begin + end) / 2;
    	//先递，分成两段，递下去 
    	MergeSort(arr, begin, mid, p);
    	MergeSort(arr, mid + 1, end, p);
    	//再归并  [begin, mid]  [mid+1, end] 把两个小段有序的序列，合并成大段有序的序列
    	Merge(arr, begin, mid, end, p);
    }
    
    //归并排序
    void MergeSort(int arr[], int size)
    {
        
    	int* p = new int[size];
    	MergeSort(arr, 0, size - 1, p);
    	delete[]p;
    }
    
    int main()
    {
        
    	int arr[10];
    	srand(time(NULL));
    
    	for (int i = 0; i < 10; i++)
    	{
        
    		arr[i] = rand() % 100 + 1;
    	}
    
    	for (int v : arr)
    	{
        
    		cout << v << " ";
    	}
    	cout << endl;
    
    	MergeSort(arr, 10);
    
    	for (int v : arr)
    	{
        
    		cout << v << " ";
    	}
    	cout << endl;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]

## 归并排序算法的性能分析 ##

**对于归并排序算法来说，没有最好和最好情况之说，因为不管是乱序还是已经有序的，都是对半分的，合成出来的都是一个非常完美的二叉树**

**时间复杂度：**  
树的层高：O(logn)，在每一层，都要进行序列数据的合并，每一层要合并的数据可以看作是n个，是O(n)  
**所以时间复杂度是O(nlogn)**  
![在这里插入图片描述][5198c30319804162859d6420e5fd3a05.png]

**空间复杂度：**  
栈上定义的变量是常量个数，和数据量的大小没有关系  
有递归，递归的深度是树的层数是logn，递归占用的内存是O(logn)  
有开辟额外的堆空间数组。是O(n)  
递归的深度和开辟额外的堆内存空间没有直接关系。  
所以，它们是相加的关系。  
![在这里插入图片描述][0993c46ed5b440fba7d974ab4d52c4a4.png]  
**所以，我们取大的那个值：O(n)**

**归并排序是稳定的：**  
![在这里插入图片描述][5a1976c3a3cc4f43bbd1a92c9886c64e.png]

**是稳定的，如果两个序列比较的两个元素的值是相等的，是先把前面序列的那个元素放进去。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]

[a41dc0055ba44504ba9bf1c8684bfaec.png]: /images/20220828/a28dc5b1414e4684899bc8c64c080951.png
[4e878e1cba164b57ac189a61074ddd20.png]: /images/20220828/04284fa6cf474f57b45f7bbbc7959bf0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/df55fb8ff72f4926a6d553617abf2b9a.png
[de9260ab509440c98ffce4b476cb5a7b.png]: /images/20220828/07dde3ffda2e428a8d108cd694e48609.png
[22074c9dba864f49aed7d8ea4323663e.png]: /images/20220828/c08055107ab44f6fbbf7828d3bb2f4d0.png
[e6a851875d9a4d4097b9933e08319126.png]: /images/20220828/b00d32e64bce476d9d4b4564424f1a9c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/f46ed1e449cc48dd80f3f7d6217e5487.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/c6cd5695149d4c719a88a0bd9e73b6f7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/79a4702a7fed4611b00cba2095952dd9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/f769f610c2404f9eab2c4fb1e63cf8b5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b69612d11f934c94891d14d505d02460.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/12ad10e630ff419a8ae0c80998d6181b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b4c403234f24470ca4456931bee59e77.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/0f9913de8bf2473cbede43778b5b0b1a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_13_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/199e23373bec4499bd0912bcc9519791.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/b6b81d36c32e4888bc6c2e74efbdf131.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/a646e0f24c3b4217b9f2a972bd22f9ff.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/ca614c7648464919957d268b9c615d8f.png
[59d93bbe744b4c65acb5e199bcbfeb84.png]: /images/20220828/6f9608bf6f5c4ea28c4c378ad5233900.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/4940b1bc37214d0a89e82f3156c16a0c.png
[5198c30319804162859d6420e5fd3a05.png]: /images/20220828/2035e666b72448ad9272146a6c28b632.png
[0993c46ed5b440fba7d974ab4d52c4a4.png]: /images/20220828/6849ef5554e64169a7af4e600fd98c9e.png
[5a1976c3a3cc4f43bbd1a92c9886c64e.png]: /images/20220828/63961e35086c4196b92a54dc0f4fce80.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/ca70974831f84486a80ed75af1bfd247.png