m数据结构 day26 排序（四）归并排序（分治法）:倒置的完全二叉树

超、凢脫俗 2023-02-16 10:59 5阅读 0赞

### 文章目录 ###

*  完全二叉树对排序的谜之天赋
 *  归并排序的根本思想：先分解为多个有序子序列，再把多个有序子序列合并为一个有序序列
 *  代码
 *   *  递归版本
     *   *  复杂度和稳定性:占用内存多，但是效率高，并且很稳定
         *   *  时间复杂度：最好，最坏，平均都是 O ( n log ⁡ n ) O(n\\log n) O(nlogn)
             *  空间复杂度： O ( n + log ⁡ n ) O(n + \\log n) O(n\+logn)
             *  两两比较无跳跃：稳定
     *  迭代版本（时空复杂度都更低，比递归更优）

# 完全二叉树对排序的谜之天赋 #

堆排序用了完全二叉树的深度信息，排序效率很高。其实，用到完全二叉树的排序算法，效率都很高。完全二叉树很适合用来排序，可能是它本身的结构的原因吧。

归并排序在某种意义上，也是利用/借助了完全二叉树，不过和堆排序利用的原理不同，它是利用了倒置的完全二叉树。比如：  
![在这里插入图片描述][20200609170454685.png]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]

# 归并排序的根本思想：先分解为多个有序子序列，再把多个有序子序列合并为一个有序序列 #

听起来好像没做啥，其实正是合并的过程在完成排序这个关键操作。分解步骤只是铺垫，为了后面和合并排序奠定物质基础（即把整个长度为n的待排序序列分解为n个长度为1的子序列。）。而且，只是代码需要分解操作，如果我们人直接拿着一个无序表企图使用归并方法排序的话，根本用不着分解，因为一开始就是分解好的呀，把他看做是n个单独的有序数据就好了。

所以合并才是最核心的操作，因为是 合并这个动作完成了排序的目标，所以名字叫做合并排序/归并排序，不叫分解合并排序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]

展示一个更完整的示例。上图只是展示了合并过程，没有展示分解的过程。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]

# 代码 #

我觉得归并排序的思想理解起来很简单，但是代码好难实现啊，我看了好几遍了，总是只能看到外层浅层的东西，看不深入，有种钻不透彻的感觉

## 递归版本 ##

/*SqList * L*/
    MergeSort(L->arr, 1, L->length);//主函数中的调用语句

/*MergeSort函数递归调用自己实现把整个无序表分解为n个长度为1的子序列*/
    //第一个参数传的是指针，不是按值传递，所以后续递归操作的都是这一个数组
    void MergeSort(int arr[], int left, int right)
    { 
    	if (left >= right)
    		return;
    	int middle = (right + left) / 2;
    	MergeSort(arr, left, middle);
    	MergeSort(arr, middle+1, right);
    	Merge(arr, left, middle, right);
    }

/*把arr数组中下标为left到middle，和下标为middle+1到right的两部分合并起来*/
    void Merge(int arr[], int left, int middle, int right)
    { 
    	int tmp[right - left + 1];//把待合并排序的数值放在这个数组里暂存备用，而排序完成的数值则存在原数组arr中
    	//从arr中获取待归并的元素，arr是待排序的整个无序表
    	for (int i=left;i<=right;++i)
    	{ 
    		tmp[i - left] = arr[i];
    	}
    	int i = left, j = middle + 1;
    	//给arr的下标left到下标right重新赋值（即赋排序完成后的值）
    	for (int k = left;k < right;++k)
    	{ 
    		//注意左边组和右边组分别都已经是有序的，这里只是合并他俩得到一个有序数组，但并未新建一个数组，而是仍然放在原数组arr中
    		if (i>middle && j<=right)
    		{ 
    			arr[k] = tmp[j - left];//左边组的数字已经排序完成，直接把右边组的剩余第一个数字放进arr
    			++j;
    		}
    		else if (j>right && i<=middle)//右边组的数字已经排序完成，直接把左边组的剩余第一个数字放进arr
    		{ 
    			arr[k] = tmp[i-left];
    			++i;
    		}
    		//依次比较left和middle+1,left+1和middle+2，直到i为middle或者j为right
    		else if (tmp[i-left] <= tmp[j-left])
    		{ 
    			arr[k] = tmp[i - left];//等于较小的那个值
    			++i;
    		}
    		else if (tmp[i-left] > tmp[j-left])
    		{ 
    			arr[k] = tmp[j - left];//等于较小的那个值
    			++j;
    		}
    	}
    }

### 复杂度和稳定性:占用内存多，但是效率高，并且很稳定 ###

#### 时间复杂度：最好，最坏，平均都是 O ( n log ⁡ n ) O(n\\log n) O(nlogn) ####

#### 空间复杂度： O ( n + log ⁡ n ) O(n + \\log n) O(n\+logn) ####

因为待排序序列的每一个元素都要被分解出来，并两两比较处理啥的，所以要O(n)时间。

整个归并排序需要和原始记录序列同样数量的存储空间来辅助，并且递归深度是 ⌈ log ⁡ 2 n ⌉ \\lceil \\log\_2 n \\rceil ⌈log2n⌉  
所以是这么多

#### 两两比较无跳跃：稳定 ####

## 迭代版本（时空复杂度都更低，比递归更优） ##

如果要用归并排序，尽量用非递归的版本。因为不仅空间复杂度更低（ O ( n ) O(n) O(n), 因为不再需要递归调用的 O ( log ⁡ n ) O(\\log n) O(logn)的栈空间），而且时间性能上也有提升。

> 我现在不喜欢递归了。之前一直觉得它的思路很智慧，把问题分解为一个个子问题，分治和回溯的思想很美丽。但是现在我慢慢发现，递归并不是简单的用空间换时间，它是时间和空间都需要的更多！！！很多个血淋淋的例子了，不忍回忆。  
> 而且能把用递归很好理解的东西转换为迭代法实现，更聪明。

迭代版本**不需要先分解**，而是像咱们人类一样，直接从最小的长度为1的序列开始归并。

void MergeSort_Iter(SqList * L)
    { 
    	int * TR = (int *)malloc(L->length * sizeof(int));
    	int k = 1;
    	while (k < L->length)
    	{ 
    		MergePass(L->r, TR, k, L->length);//把长度为k的子序列归并为长度为2k的子序列
    		k = 2 * k;//子序列长度加倍
    		MergePass(TR, L->r, k, L->length);
    		 k = 2 * k;//子序列长度加倍
    	}
    }

/*实现归并,把SR数组中两个相邻的长度为s的子序列两两归并到TR数组*/
    void MergePass(int SR[], int TR[], int s, int n)
    { 
    	int i = 1;
    	int j;
    	while (i <= n-2*s+1)
    	{ 
    		Merge(SR, TR, i, i+s-1, i+2*s-1);
    		i = i + 2*s;
    	}
    	if (i<n-s+1)
    		Merge(SR, TR, i, i+s-1, n);
    	else
    		for (j=i;j<=n;++j)
    			TR[j] = SR[j];
    }

//把有序的SR[i, ```, m]和有序的SR[m+1,```, n]归并为有序的TR[i,```,n]
    void Merge(int SR[], int TR[], int left, int middle, int right)
    { 
    	int j,k,q;
    	//比较left和middle+1, left+1和middle+2···
    	for (j=middle+1, k=left;left<=middle && j<=right;++k)
    	{ 
    		if (SR[left] < SR[j])
    			TR[K] = SR[left++];
    		else 
    			TR[k] = SR[j++];
    	}
    	//比较和归并结束后(左边组没数字或者右边组没数字了)
    	if (left<=middle)//右边组更短，右边组没数字了，把左边组的剩余有序数字SR[left,```,middle]直接复制到TR即可
    	{ 
    		for(q=0;q<middle-left;++q)
    			TR[k+1] = SR[left+1];//
    	}
    	if (j <= right)//左边组没数字了，右边还有,把SR[j,```,right]复制到TR
    	{ 
    		for (q=0;q<right-j;++q)
    			TR[k+q] = SR[j+q];
    	}
    }

[20200609170454685.png]: https://img-blog.csdnimg.cn/20200609170454685.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/202006091705077.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200609170630547.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200610112332372.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70