9.6 归并排序慕课视频播放-数据结构-MOOC慕课视频教程-柠檬大学

同学们大家好

我是云南大学信息院教师孔兵

这节课我们介绍归并排序

“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表

假设初始序列含有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.算法概念导入

--1.1 算法概念导入

-2.数据结构课程介绍

--2.数据结构课程介绍

-数据结构前言PPT

第0章预备知识

-0.1变量、类型和表达式

-0.2 函数

-0.3 指针和单链表

-0.4 数组、指向函数的指针

第1章绪论

-1.1什么是数据结构

--1.1什么是数据结构

--测试题

-1.2基本概念和术语

--1.2基本概念和术语

--测试题

-1.3数据结构的描述

--1.3数据结构的描述

--测试题

-1.4抽象数据类型的定义和实现

--1.4抽象数据类型的定义和实现

--测试题

-1.5算法和算法分析概念

--1.5算法和算法分析概念

--测试题

-1.6算法分析示例

--1.6算法分析示例

--测试题

-第1章绪论讨论题

-数据结构第1章绪论PPT

第2章线性表

-2.1 线性表的类型定义

--2.1线性表的类型定义

--测试题

-2.2线性表的顺序表示和实现

--2.2 线性表的顺序表示和实现

--测试题

-2.3 线性链表

--2.3 线性链表

--测试题

-2.4 静态链表

--2.4 静态链表

--测试题

-2.5 循环链表和双向链表

--2.5 循环链表和双向链表

--测试题

-第2章线性表讨论题

-数据结构第2章线性表PPT

第3章栈和队列

-3.1 栈

--3.1栈

--测试题

-3.2 栈的实现

--3.2 栈的实现

--测试题

-3.3 栈的应用

--3.3 栈的应用

-3.4 栈与递归的实现

--3.4栈与递归的实现

--测试题

-3.5 队列和链队列

--3.5 队列和链队列

--测试题

-3.6 循环队列

--3.6 循环队列

--测试题

-第3章栈和队列讨论题

-数据结构第3章栈和队列PPT

第4章串

-4.1 串

--4.1 串

--测试题

-数据结构第4章串PPT

第5章数组

-5.1 数组定义和表示

--5.1 数组定义和表示

--测试题

-5.2矩阵的压缩存储

--5.2 矩阵的压缩存储

--测试题

-第5章数组讨论题

-数据结构第5章数组PPT

第6章树和二叉树

-6.1 树的定义和基本术语

--6.1 树的定义和基本术语

-6.2 二叉树和二叉树的性质

--6.2 二叉树和二叉树的性质

--测试题

-6.3 二叉树的存储结构

--6.3二叉树的存储结构

--测试题

-6.4 遍历二叉树

--6.4 遍历二叉树（1）

--6.4 遍历二叉树（2）

--测试题

-6.5 线索二叉树

--6.5 线索二叉树

--测试题

-6.6 树的存储

--6.6树的存储

-6.7 树的转换和遍历

--6.7 树的转换和遍历

--测试题

-6.8 赫夫曼树

-6.9 赫夫曼编码

--测试题

第7章图

-7.1 图的定义和术语

--7.1.1图的定义和术语（1）

--7.1.2图的定义和术语（2）

--测试题

-7.2 图的存储结构

--7.2.1 数组表示法（1）

--7.2.2 数组表示法（2）

--7.2.3 邻接表

--测试题

-7.3 图的遍历

--7.3.1 深度优先搜索

--7.3.2 广度优先搜索

--测试题

-7.4 最小生成树

--7.4.1 普里姆算法

--7.4.2 克鲁斯卡尔算法

--测试题

-7.5 有向无环图

--7.5.1 拓扑排序

--7.5.2 关键路径

--测试题

-7.6 最短路径

--7.6.1 单源最短路径-迪杰斯特拉算法

--7.6.2 每一对顶点之间的最短路径-弗洛伊德算法

--测试题

-第7章图讨论题

-数据结构第7章图PPT

第8章查找

-8.1 查找基本概念和顺序查找

--8.1 查找基本概念及顺序查找

--测试题

-8.2 有序表的查找

--8.2 有序表的查找

--测试题

-8.3 二叉排序树

--8.3.1 二叉排序树（1）

--8.3.2 二叉排序树（2）

--测试题

-8.4 平衡二叉树

--8.4 平衡二叉树

--测试题

-8.5 哈希表

--测试题

第9章内部排序

-9.1插入排序

--9.1.1 插入排序（1）

--9.1.2 插入排序（2）

--测试题

-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 排序方法总结

--9.8 排序方法总结

-第9章内部排序讨论题

-数据结构第9章内部排序PPT

9.6 归并排序在线视频

9.6 归并排序课程教案、知识点、字幕

数据结构课程列表：

前言

第0章预备知识

第1章绪论

第2章线性表

第3章栈和队列

第4章串

第5章数组

第6章树和二叉树

第7章图

第8章查找

第9章内部排序

9.6 归并排序笔记与讨论

也许你还感兴趣的课程:

9.6 归并排序在线视频

9.6 归并排序课程教案、知识点、字幕

数据结构课程列表：

前言

第0章 预备知识

第1章 绪论

第2章 线性表

第3章 栈和队列

第4章 串

第5章 数组

第6章 树和二叉树

第7章 图

第8章 查找

第9章 内部排序

9.6 归并排序笔记与讨论

也许你还感兴趣的课程:

第0章预备知识

第1章绪论

第2章线性表

第3章栈和队列

第4章串

第5章数组

第6章树和二叉树

第7章图

第8章查找

第9章内部排序