当前课程知识点：数据结构 > 第8章 排序 > 8.5 归并排序 > 讲解
本节，我们来学习最后一类排序算法，归并排序
归并排序，是将多个有序的子序列，合并为一个有序序列
通常，我们是将2个有序的子序列，合并为一个有序序列
这时候的归并，叫做2路归并
我们将待排的序列，划分成n个子序列
也就是说，每个子序列仅仅包含一个元素
我们知道，一个元素的子序列
它总是有序的
接下来，我们合并相邻位置的2个子序列
最终，子序列的个数会由n个
变成n/2向上取整
因为，n可能是奇数
所以，我们是向上取整
我们把这样的过程，称为一趟归并
一直往下，一共执行log2(n)向上取整这么多趟归并
最终，就可以得到一个长度为n的有序序列
现在，我们来看一个例子
比如，这7个元素
我们将它的每一个元素，作为一个子序列
现在，7个元素就分成了7个子序列
然后，我们将相邻位置的2个子序列合并
比如[4]、[3]，合并成一个有序的[3,4]
接着，再去合并
然后，继续下一趟相邻位置的子序列合并
[3,4]、[5,7]合并成一个[3,4,5,7]，[1,6]、[2]合并成[1,2,6]
最后一趟，我们就合并得到的两个有序的子序列
这样，我们就得到了最终正序排列的序列
一趟归并(一趟合并)，它的算法又如何进行呢
其实，跟我们前面讲的两个多项式相加，是类似的
只不过当时，2个多项式采用的是链式存储
因为，我们是按照项的指数递增排列的
所以它也是有序的
我们现在采用顺序存储，第一个有序的子序列，是low到m
第二个有序的子序列，是m+1到high
现在，我们拿i、j分别指向两个有序序列的下界
也就是low和m+1，然后，比较i和j指向的元素谁小一些
因为我们要排成正序
谁小，我们就把那个值插入到T当中
我们用T，来存放合并之后的那个序列
p指向T当中的插入位置
记住,i、j指向的值
谁小，就把谁插入到T当中
i和j如果有一个超过了各自序列的范围
我们就将另外一个序列当中剩下的那些元素，全都复制到T当中，就可以了
这完全是跟我们前面讲的多项式相加，是一样的
对2个子序列进行归并
我们可以递归到，对它们各自划分出来的2个子序列进行归并
比如，我们现在要归并2个子系列
左边的这个子序列
我们再一分为二
相当于递归
那你一直往下递归
当子序列长度是1的时候
也就是，划分出来的子序列长度为1
仅仅包含1个元素的时候
这时候，就不需要递归了
因为，一个元素总是有序的
所以，终结条件就是子序列长度为1
现在，我们来看具体的算法实现
归并排序，mergeSort
我们对L进行归并排序
把最后的结果放到T当中
T的容量，很明显，跟L是一样的
L的下界是low，上界是high
我们声明了几个变量
if语句，如果low小于high
说明，序列长度至少是2
如果是1
low和high是相等的
序列长度至少包含2个元素
我们就要进行递归
我们计算出中间位置
然后，分别对左子序列和右子序列进行递归
左子序列的下界是low，上界是m
这地方是整除，它会向下取整的
右子序列的下界是m+1，上界是high
就是以m为中间位置，划分成左、右两个子序列
然后进行递归，终结条件实际上是low等于high
也就是，序列仅仅包含一个元素
也就是说
程序执行到这里，表示左、右子序列已经排好序了
或者说，仅仅包含一个元素
这时候，我们就应该合并了
后面即将讲的合并算法，就是我们刚才说的
类似于多项式相加的那个算法
首先，我们用i、j分别指向
两个子序列的下界，也就是low和m+1
p指向用来存放合并结果的T的起始位置，也就是low
现在，当i小于等于m，并且j小于等于high的时候
因为，i、j(指向的2个子序列的下标)都是从1开始的
当这二者同时成立
意味着，左、右区间(子序列)的元素尚未处理完毕
那我们就要比较，i指向的和j指向的谁小
如果i指向的小于等于j(指向的)
我们就将i指向的那个元素，放到T的p位置
注意，是后置的自增
后置的自增
谁小就放谁
else，意味着，i指向的要大一些
那我们就放j指向的
把它放到p的位置
当这个while循环结束的时候
也就是，i大于m，或者j大于high
这时候，我们就要判断一下
还有哪一个子序列当中有剩余元素
没有插入到T当中
如果是i小于等于m
意味着，第一个子序列还有剩余元素，未插入到T当中
那我们就做循环，把第一个子序列当中剩余的元素，放到T当中，就可以了
与之对称的
如果是第二个子序列当中，还有元素未被插入到T当中
我们就将第二个子序列当中剩余的元素，放到T当中
最后，有一个for循环
这个for循环，实际上，就是用来将存放合并之后的那个序列T当中所有的元素，还原到L当中
因为，最终结果还是要存到L当中的
因为，我们是对L进行排序
这实际上，是将T复制回L
这个算法它的时间复杂度
刚才我们已经分析过了
n个元素，一共要经历log2(n)趟归并，才能排好序
每一趟，我们就看最后这个for循环
它总要复制n个元素
所以，它的时间复杂度就是n*log2(n)
空间复杂度
这里，算法用到的空间，实际上分为两部分
第一部分，是这个T所占的空间
因为，我们要临时存放合并之后的序列
它的长度跟L的长度，是一样的，是n
另外，这个算法用到了递归
它也要占据log2(n)这么深的递归工作栈
所以，这个算法的空间复杂度，是O(n)
归并排序是一个稳定的排序
我们可以这样分析
这个if语句，如果r[i]是小于等于r[j]的
注意，i是指向左子序列的，j是指向右子序列的
左子序列的元素小于等于，如果等于
它也是将左子序列的元素，插入到T当中
归并前后，那些相等的元素
实际上，它们的先后位置，是不会发生变化的
原来在左边的，它在T当中，也是在左边
如果你把这里的等号去掉
也就是说，相等的时候，执行这个else
我们插入右边的那个元素
这时候，它就变成不稳定的了
这也验证了我们前面讲的，稳定的排序算法，都能改成不稳定的
我们这里，还是写上等号
所以，归并排序，它是一个稳定的排序
同学们，本门课程到此，就全部结束了
大家在学习过程中
如果有任何的疑问或建议，欢迎在平台上与我们交流
我们将及时地回复，感谢大家的一路陪伴
谢谢！
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
