nbhkdz.com冰点文库

2.1.2排序问题与算法的多样性

时间:2015-06-11


排序问题与算法的多样性

导入

你会不会从图 书馆中寻找到 你想要的书籍?

为了便于查询和检索,我们常常根据需要将被查寻的对象按照一 定的顺序排列,通常称为排序. 按照某种顺序排列的数据列为有序列.

导入 问题:将 3 插入到有序列 { - 3, - 2,2,4,7} 中, 你能 想到几种排

序方法?
提示:两种方法:有序列直接插入排序和有序列折半插入排序. 方法一:已知数列由小到大(或由大到小)排列整齐,再将 3从右向左逐个与有序列中数据比较,确定3在排列中的位 置,该位置的两侧数字必须满足: 左边小于等于(大于等于)3,右边大于等于(小于等于)3.

-3 -2 2

3

4

7

此方法叫作有序列直接插入排序.

导入
方法二 :首先选择有序列的“中间位置”数据 2, 将 3 与 2 进 行 比 较 , 显 然 3>2, 所 以 3 应 排 在 2 的 右 边 :{-3,2,2,3,4,7}. 然后取余下数据列{4,7}的“中间位置”的数据4与3比较, 显然3<4,因此3应插到4的左边:{-3,-2,2,3,4,7}.
此方法叫作有序列折半插入排序.

思考—有序列的排列问题
问题 : 把数据 52 插入到有序列 {13,27,51,57,82} 中构成一个新的有序列.
解法一: 1.比较52与82, ∵ 52 <82∴52放82 左边; 2.比较52与57, ∵ 52 <57∴52放57左边; 3.比较52与51, ∵ 52 >51∴52放51与57中间; 4.得到新有序列{13,27,51,52,57,82}.

解法二:
a1 13 a2 27 a3 51 a4 57 a5 82

首先选择有序列的“中间位置”数据a3=51,将52与51进 行比较,显然52> 51,所以52应排在51的右边:
a1 13 a2 27 a3 51 52 a4 57 a5 82

然 后 取 余 下 数 据 列 {57,82} 的 “ 中 间 位 置 ” 的 数 据 a4=57与52比较,显然52<57,因此52应插到57的左边:
a1
13

a2
27

a3
51

a4
52

a5
57

a6
82

归纳 · 概括
1.有序列直接插入排序法蕴涵的算法思想:
有序列直接插入法主要是通过逐一比较,通过有限次 的“操作”将某一个数据插入原有序列的一种算法,它主要 包含以下两步: 对于一个有序列:a1≤a2≤a3≤…≤an,欲将新数据 A插入 到有序列中,形成新的有序列. ①将数据A与原有序列中的数据从右到左依次进行比 较,直到发现某一数据ai,使得ai≤A,把A插入到ai的右边; ②如果数据 A小于原有序列中的所有数据,则将 A插 入到原序列的最左边.

归纳 · 概括
2.有序列折半插入排序法蕴涵的算法思想及插入的方

法和步骤:
折半插入排序的基本思想与二分法的思想一致,即 逐步缩小所要比较的数据的范围,直到确定出所要插入 的数据的位置为止.插入的方法如下: ①先将新数据与有序列中 “ 中间位置 ” 的数据进行 比较: 若有序列有2n+1个数据,则“中间位置”的数据指 的是第n+1个数;若有序列有2n个数据,则“中间位置 ”的数据指的是第n个数.

归纳 · 概括
②如果新数据小于 “ 中间位置 ” 的数据,则新数据 插入的位置应该在靠左边的一半;如果新数据等于 “中 间位置”的数据,则将新数据插入到“中间位置”的数据 的右边;如果新数据大于 “ 中间位置 ” 的数据,则新数 据插入的位置应该在靠右边的一半. 也就是说,一次比较就排除了数据列中一半的位 置,反复进行这种比较直到确定新数据的位置,像这 样的插入排序方法就称为折半插入排序方法.

练习
分别用两种方法将数据 210插入到有序列{6,56,98,114,156,320,421} 中,用自然语言写出排序算法的步骤. 解法1(直接插入法): ⑴比较210与421,∵210<421∴210放421左边; ⑵比较210与320,∵210<320∴210放320左边; ⑶比较210与156,∵210>156∴210放156和320之间; ⑷得到新的有序列{6,56,98,114,156,210,320,421}. 解法2 (折半插入法): ⑴取有序列中间数114<210; ⑵取114右边有序列中间数320>210; ⑶取320左边有序列中间数156<210; ⑷将210插入到156和320之间; ⑸得出新的有序列.

思考—无序数据排序 问题:将无序列{1,17,5,12,8,25,15}按照从小到 大的顺序,用自然语言写出排序算法的步骤.
提示:参考有序列排序算法的思想.
从左向右, 将无序列的第一个数据看成的一个序列 {1},将 17插入有序列{1}中,得到两个数据的有序列:{1,17}; 将第三个数据5插入到{1,17}中,得到有序列:{1,5,17}; ? ?. 按 照 这 种 方 法 , 知 道 最 后 一 个 数 据 15 插 入 到 有 序 列 {1,5,8,12,17,25}中,得到有序列{1,5,8,12,15,17,25}. 这样我们就完成了整个排序工作 , 可以看出 , 有序列插入 排序算法是解决这个问题的关键.

课堂小结

?有序列折半插入排序的思想和算法 ?有序列直接插入排序的思想和算法 ?无序数据的排序问题


1.2第2课时细胞的多样性和统一性

1.22课时细胞的多样性和统一性_理化生_高中教育...2- 规律计算;②圆形视野范围内细胞数量的变化,可...迁移训练 1:使用高倍镜的观察顺序是( ) ①调节细...

1.2细胞的多样性和统一性

1.2细胞的多样性和统一性_理化生_高中教育_教育专区...2.问题探讨 (1)为什么要先用低倍镜观察清楚后,把...节节过关达标检测 1.使用高倍镜的观察顺序是( ) ...

1.2.2 细胞的多样性和统一性_图文

第 3 课时 细胞的多样性和统一性 2 课型:新授课 一、目标与问题 1、能...生物界的多样性 例 3、下列有关“细胞学说”建立过程中的顺序中,正确的是( ...

1.2细胞的多样性和统一性

1.2细胞的多样性和统一性_高二理化生_理化生_高中...问题 2:出示一个大肠杆 菌的照片和结构示意图,它...看到的实物范围与放大倍数的平 方成反比的规律计算...

1、2细胞的多样性和统一性学案

2 1.2 细胞的多样性和统一性班级 姓名 【学习...— [问题探讨 ] 展示多种细胞图片,观察后思考问题...正确的操作顺序是 A.①②③④ B.②①④③ ( )...

1.2 自制 细胞的多样性和统一性导学案

使用高倍显微镜观察装片的顺序是 ①转动转换器把低倍镜移走,换上高倍镜 ②在...生物知识超市 第 1 章 走进细胞 第 2 节 细胞的多样性和统一性 ()问题...

1.2细胞的多样性和统一性(导学案)

细胞的多样性和统一性【教学目标】 1.说出原核细胞...问题探讨 观察课本的四幅图,你能分辨 出它们分别是...计算 【典型例题】〖例 1〗使用高倍镜的观察顺序...

1.2 细胞的多样性和统一性自学案

——赵家铎 细胞的多样性和统一性自 1.2 细胞的...的变化,可根据细胞数目与放大倍数成反比的规律 计算...(2)时,操作过程中的正确顺序是( ) 8.关于蓝藻的...

必修2专题1 从微观结构看物质的多样性(五校—刘浪)

看物质的多样性 授课日期及时段 1、从同素异形现象认识物质的多样性 2、从...按熔点由低到高排列正确的是 () A、O2、I2、Hg B、CO2、KCl、SiO2 C、...

1-2 第2节 细胞的多样性和统一性及章测试

合作探究】 【合作探究】 问题一: 问题一:细胞的多样性和统一性 1、教材第 ...(2)在目镜为 10×、物镜为 8×的视野中,看到刚好穿过视野中心的一行连续排列...