当前课程知识点:数据结构 > 第9章 内部排序 > 9.6 归并排序 > 9.6 归并排序
同学们大家好
我是云南大学信息院教师孔兵
这节课我们介绍归并排序
“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表
假设初始序列含有n个记录
则可看成是n个有序的子序列
每个子序列长度为1,然后两两归并
得到n/2(向上取整)个长度为2或1的有序子序列
再两两归并,·······,如此重复
直至得到一个长度为n的有序序列为止
因为每次都是把两个有序的子序列归并为一个有序的序列
这种排序方法被称为2-路归并排序
通过一个例子看一下归并的过程
初始序列如图1所示,序列中含有7个记录
把长度为1的7个子序列做两两归并
就是把1和2,3和4,5和6两两归并
7单独,获得如图2所示的4个长度为2和1的子序列
随后把前面长度为2的两个子序列归并
后面长度为2和1的两个子序列归并
获得如图3所示的两个长度为4和3的有序序列
最后再对这两个序列进行归并
获得如图4所示的有序序列,完成整个序列的排序
请同学们思考,归并排序是否稳定?
下面看一下二路归并排序的实现
我们介绍两个函数,第一个函数是merge
其作用是把数组中相邻的两个有序子序列
归并为一个有序序列
merge的参数有5个
数组SR中的一段区间存储相邻的两个有序子序列
两个子序列归并后,存到第2个参数
数组TR相应的区间
3个整型参数i, m, n给出两个子序列在SR中的区间
参数的含义是:把数组SR中,从i到m和从m+1到n
这两段有序的子序列归并为有序序列
归并后的有序序列存储到数组TR中从i到n这一段
具体的归并过程第2章中有详细讨论,这里不说了
第二个函数是MSORT,其作用是完成数组中一段区间的排序
Msort的函数有4个,数组SR中存储待排序序列
数组TR1存储排序后的序列
2个整型参数s和t指明SR中要排序的区间低端和高端
参数的含义是:把数组SR中从s到t这段进行排序
排好后存放在数组TR1中从s到t这段
函数中是一个if-else语句,如果s等于t
说明序列中只有一个记录,不必其它操作
SR[s]赋值给TR1[s]即可
否则,求s到t区间的中点赋值给m
递归调用自己,分别对序列的前半段s到m
和后半段m+1到t进行排序,递归返回后
调用merge把已经排好序的前半段和后半段归并为一段
存到TR1中,完成s到t这段区间的排序
要完成整个序列的排序,只需要调用Msort
把1和L.length作为实参传递个形参s和t就可以了
好同学们,归并排序我们就讨论到这
下次课再见
-1.算法概念导入
-2.数据结构课程介绍
-0.1变量、类型和表达式
-0.2 函数
--0.2 函数
-0.3 指针和单链表
-0.4 数组、指向函数的指针
-1.1什么是数据结构
--测试题
-1.2基本概念和术语
--测试题
-1.3数据结构的描述
--测试题
-1.4抽象数据类型的定义和实现
--测试题
-1.5算法和算法分析概念
--测试题
-1.6算法分析示例
--测试题
-2.1 线性表的类型定义
--测试题
-2.2线性表的顺序表示和实现
--测试题
-2.3 线性链表
--2.3 线性链表
--测试题
-2.4 静态链表
--2.4 静态链表
--测试题
-2.5 循环链表和双向链表
--测试题
-3.1 栈
--3.1栈
--测试题
-3.2 栈的实现
--3.2 栈的实现
--测试题
-3.3 栈的应用
--3.3 栈的应用
-3.4 栈与递归的实现
--测试题
-3.5 队列和链队列
--测试题
-3.6 循环队列
--3.6 循环队列
--测试题
-4.1 串
--4.1 串
--测试题
-5.1 数组定义和表示
--测试题
-5.2矩阵的压缩存储
--测试题
-6.1 树的定义和基本术语
-6.2 二叉树和二叉树的性质
--测试题
-6.3 二叉树的存储结构
--测试题
-6.4 遍历二叉树
--测试题
-6.5 线索二叉树
--测试题
-6.6 树的存储
--6.6树的存储
-6.7 树的转换和遍历
--测试题
-6.8 赫夫曼树
--6.8 赫夫曼树
-6.9 赫夫曼编码
--测试题
-7.1 图的定义和术语
--测试题
-7.2 图的存储结构
--测试题
-7.3 图的遍历
--测试题
-7.4 最小生成树
--测试题
-7.5 有向无环图
--测试题
-7.6 最短路径
--测试题
-8.1 查找基本概念和顺序查找
--测试题
-8.2 有序表的查找
--测试题
-8.3 二叉排序树
--测试题
-8.4 平衡二叉树
--测试题
-8.5 哈希表
--测试题
-9.1插入排序
--测试题
-9.2 希尔排序
--9.2 希尔排序
--测试题
-9.3 快速排序
--9.3 快速排序
--测试题
-9.4 选择排序
--9.4 选择排序
--测试题
-9.5 堆排序
--9.5 堆排序
--测试题
-9.6 归并排序
--9.6 归并排序
--测试题
-9.7 基数排序
--9.7 基数排序
--测试题
-9.8 排序方法总结