当前课程知识点：程序设计基础 > 第五章分治思想与递归 > 5.2 排序 > 5.2.1 归并排序——总体思路

返回《程序设计基础》慕课在线视频课程列表

5.2.1 归并排序——总体思路在线视频

5.2.1 归并排序——总体思路

下一节:5.2.2 归并排序——思路分解

返回《程序设计基础》慕课在线视频列表

5.2.1 归并排序——总体思路课程教案、知识点、字幕

我们在前一章给大家介绍了用折半查找

快速的来查找某个元素的这种方法

当时我们提到在这样的一个方法

必须要求这个数组是有序的

那么然后我们介绍了一个插入排序

选择排序这样的一个办法

那么这个折半的查找

它之所以看起来查找非常的快速

是因为它只查了

在迭代的时候只查了一半

另外一半它其实没有去做

那么这样的一个把一个任务拆成两个部分只完成其中的一部分

这是一个很有效的一种办法

所以我想呢下面给大家介绍的是跟这个方法有点类似的

但是又不完全一样的

一种新的想法然后让它来完成这个排序的过程

那么它是怎么做的呢

我们新来看这个数组

那么假设这个数组里头有一批元素

我们要对它进行排序

那刚才我们提到

折半查找之所以快

是因为它把任务拆开了

而且呢它有效的利用

这个数组里头元素的有序性只查找了一半

那么这样的一个思想呢我们可以把它借鉴过来

我们可以这样子提出一个想法

能不能把这个数组也给它

无论你有序没序

我为了让你有序我可以把它拆开

每人完成一部分

也就是像大家现在看到的样子

把这个数组从中间一分为二

左边是一个数组

右边是一个数组

那很显然这两个数组都比原来的那个大数组要短

那所以它里头在这个排序的过程

就会比原来的要快

这个很简单的情形

假如说这个元素值这个数组只有一个元素

那你不用排它肯定是有序的

所以当元素多了

它的运算就会时间消耗啊等等就会比较复杂

那么为了让这个任务更简单

我们把它分成了两个数组

那么如果我们把两个数组已经排好序

那么至于怎么排好序我们待会会来讲

那假定我们现在从思路上来看

假定这两个数组已经排好序了

那我怎么让它最终的那个数组是有序的呢

也就是从两个已经有序的子数组怎么

合成了一个整体有序的大数组呢

这个其实是一个把两边的子数组

合并成一个大数组的一个操作过程

那么这个算法也不难想到

我们其实是可以通过

不断的去枚举这两个数组里头的元素

去依次的比较它们

把最头上的

最小的放到一个地方存起来

然后再来查下一个

这样依次进行下去就可以把它

在一个新的地方插入成一个有序的

所以这样的一个合并的过程

其实是依次去查找两个子有序的数组

把它合并起来得到一个新的数组

就得到一个完全有序的新数组

那这样的一个过程其实是可以

迭代的进行下去

也就是说可以反复的进行

那根据我们这一章前面大家看到的

这个其实是可以采用一种递归的方法来实现

也就是先假定两个数组是有序的

然后再来把它们合并起来

那这两个数组怎么让它有序呢

这不就又退回到我现在正在解决的这个问题本身了吗

那我现在要解决的是把一个数组排序

而我刚才叙述的这个排序的过程是这样叙述的

把一个数组的前一半让它有序

后一半让它有序

然后把它们合起来

从而成为一个完全有序的一个数组

达到你的任务的要求

那你看前面的要求把前一半排序

后一半排序也是一个数组排序的过程

所以这是一个非常典型的递归的一种思路

程序设计基础课程列表：

第一章编程初步

-1.1 基础知识

--1.1.1 什么是程序？什么是语言？

--1.1.2 什么是程序设计？

--1.1.3 计算机发展史

-1.2 买菜问题

--1.2.1 问题描述

--1.2.2 程序的基本结构

-1.3 数学运算

--1.3.1 数学运算符

--1.3.2 数学函数

-1.4 补充说明

--1.4.1 编程环境的下载与安装

--1.4.2 程序基本结构中的含义

--1.4.3 格式与风格

-1.5 总结

-程设论道

-师生问答

--师生问答一：怎样学好程序设计

--师生问答二：语言选择

--师生问答三：关于函数

-第一章编程初步--语法自测

第二章变量与代数思维

-2.1 关于超级计算器的几点思考

--2.1.1 关于超级计算器的几点思考

-2.2 电子秤模拟 — 背景介绍及需求分析

--2.2.1 电子秤模拟 — 背景介绍及需求分析

-2.3 电子秤模拟 — 代码实现

--2.3.1 电子秤模拟 — 代码实现

-2.4 变量定义与变量类型

--2.4.1 变量定义与变量类型

-2.5 猜数游戏与数据表示

--2.5.1 猜数游戏与数据表示

-2.6 关于变量的讨论

--2.6.1 变量的初始值

--2.6.2 变量类型

--2.6.3 变量内存单元地址

--2.6.4 存“变量地址”的变量——指针

--2.6.5 指针的读/写操作

--2.6.6 指针的加/减操作

-2.7 变量体现的计算思维

--2.7.1 变量体现的计算思维

-程设论道

-师生问答

-第二章变量与代数思维--语法自测

第三章逻辑推理与枚举解题

-3.1 谁做的好事——语义表示

--3.1.1 谁做的好事——语义表示

-3.2 谁做的好事——真假检查

--3.2.1 谁做的好事——真假检查

-3.3 谁做的好事——循环枚举

--3.3.1 谁做的好事——循环枚举

-3.4 谁是嫌疑犯——多重循环枚举

--3.4.1 谁是嫌疑犯——多重循环枚举

-3.5 谁是嫌疑犯——破案线索表示

--3.5.1 谁是嫌疑犯——破案线索表示

-3.6 谁是嫌疑犯——用二进制枚举

--3.6.1 谁是嫌疑犯——用二进制枚举

-程设论道

--程设论道一

--程设论道二

--程设论道三

-师生问答

--师生问答一：字符与ASCII码表

--师生问答二：其他循环语句、运算符优先级与变量作用域

-第三章逻辑推理与枚举解题--语法自测

第四章筛法与查找

-4.1 插花游戏

--4.1.1 问题提出（求素数）

--4.1.2 函数初探

--4.1.3 运行演示

-4.2 筛法

--4.2.1 筛法思路

--4.2.2 数组的定义

--4.2.3 代码翻译

--4.2.4 运行演示

--4.2.5 小朋友数人数

--4.2.6 运行演示

--4.2.7 韩信点兵

-4.3 线性查找

--4.3.1 扑克查找问题

--4.3.2 扑克查找问题代码翻译

--4.3.3 最小值问题

--4.3.4 最小值问题代码翻译

-4.4 折半查找

--4.4.2 折半查找思路

--4.4.3 折半查找代码翻译

--4.4.4 折半查找运行演示

-4.5 排序问题

--4.5.1 插入排序

--4.5.2 选择排序

--4.5.3 函数写法

--4.5.4 运行演示

-4.6 总结

-程设论道

--程设论道一：数组与编码思维

--程设论道二：筛法

-师生问答

--师生问答一：函数与面向过程编程

--师生问答二：数组的下标越界

-第四章筛法与查找--语法自测

第五章分治思想与递归

-5.1 阶乘

--5.1.1 阶乘问题

--5.1.2 递归解法

--5.1.3 递归小结

-5.2 排序

--5.2.1 归并排序——总体思路

--5.2.2 归并排序——思路分解

--5.2.3 归并排序——代码解说

--5.2.4 快速排序——总体思路

--5.2.5 快速排序——代码解说

--5.2.6 排序总结

-5.3 矩阵填充

--5.3.1 矩阵填充问题

--5.3.2 代码解说

-5.4 分书与八皇后

--5.4.1 问题描述

--5.4.2 问题分析——共性

--5.4.3 问题分析——区别

--5.4.4 解题准备——二维数组

--5.4.5 解题准备——递归设计

--5.4.6 代码解说——分书问题

--5.4.7 代码解说——八皇后问题

-5.5 青蛙过河

--5.5.1 问题描述

--5.5.2 问题分析——简单情况

--5.5.3 问题分析——复杂情况

--5.5.4 问题分析——一般情况

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答一

--师生问答二

-第五章分治思想与递归--语法自测

第六章递推与动态规划

-6.1 兔子数列问题

--6.1.1 问题描述

--6.1.2 按大小兔子分别递推

--6.1.3 按总数递推

--6.1.4 不用数组递推

-6.2 分鱼问题

--6.2.1 问题描述

--6.2.2 从A到E递推

--6.2.3 从E到A递推

-6.3 橱窗的插花问题

--6.3.1 问题描述

--6.3.2 题意理解与分析

--6.3.3 用枚举思想解题

--6.3.4 采用递推的优化算法

--6.3.5.1 采用动态规划算法—优化分析

--6.3.5.2 采用动态规划算法—递推代码

--6.3.5.3 采用动态规划算法—计算过程

--6.3.5.4 采用动态规划算法—输出方案

--6.3.6 动态规划总结

-6.4 最长公共子序列问题

--6.4.1 问题描述与理解

--6.4.2 问题分析

--6.4.3.1 动态规划解题(1)

--6.4.3.2 动态规划解题(2)

--6.4.3.3 动态规划代码

-程设论道

--程设论道一

--程设论道二

-师生问答

-第六章递推与动态规划--语法自测

第七章文本数据处理

-7.1 统计记录总数

--7.1.1 问题分析

--7.1.2 读文件操作

-7.2 统计活跃用户数

--7.2.1 问题分析

--7.2.2 字符串

--7.2.3 程序翻译与演示

-7.3 统计在线时长

--7.3.1 问题分析

--7.3.3 程序翻译与演示

--7.3.4 写文件操作

-7.4 总结

-程设论道

-师生问答

-第七章文本数据处理--语法自测

第八章非文本数据处理

-8.1 将数据组织成链表

--8.1.1 链表的基本概念

--8.1.2 代码讲解

--8.1.3 链表遍历与释放

-8.2 提高链表访问效率 —— 哈希链表

--8.2.1 简单的哈希算法

--8.2.2 算法实现

-8.3 以二进制文件存储链表

--8.3.1 二进制文件的操作方法

--8.3.2 代码讲解

-程设论道

--程设论道一

--程设论道二

-师生问答

-第八章非文本数据处理--语法自测

第九章可配置的程序设计

-9.1 自动售卖程序

--9.1.1 提出问题与初步设计

--9.1.2 细化实现订单处理

--9.1.3 使程序更健壮

-9.2 配制水果信息

--9.2.1 提出问题与设计文件格式

--9.2.2 实现订单处理功能

-9.3 指定界面语言

--9.3.1 提出问题与命令行参数

--9.3.2 实现程序功能

-程设论道

-师生问答

-第九章可配置的程序设计--语法自测

5.2.1 归并排序——总体思路笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。