212排序问题与算法的多样性
《212排序问题与算法的多样性》由会员分享,可在线阅读,更多相关《212排序问题与算法的多样性(1页珍藏版)》请在装配图网上搜索。
1、2.1.2排序问题及算法的多样性教学目标:1掌握数据排序的原理能使用直接排序法给一组数据排序,进而能设计理解数学算法与计算机算法的区别,理解计算机对数学的辅助作用。教学重点:排序法的排序步骤教学难点:排序法的计算机程序设计教学过程 排序排序的算法很多,课本主要介绍里两种排序方法:直接插入排序和折半插入排序1、有序列直接插入排序基本思想:插入排序的思想就是读一个,排一个。将第个数放入数组的第个元素中,以后读入的数与已存入数组的数进行比较,确定它在从大到小的排列中应处的位置将该位置以及以后的元素向后推移一个位置,将读入的新数填入空出的位置中(由于算法简单,可以举例说明)2、折半插入排序基本思想:先
2、与一组数据中间位置的数比较,类似于二分法的算法思想。练习:例1 已知有序列158,159,160,162,163,165,166,170,171,172,175,设计算法将169插入,使其从小到大排列,构成新的数据列。分析:这是一个有序列,可采用直接插入排序法一个一个的比较进行排序,也可用折半排序法进行排序。解法一:有序列直接插入排序,步骤如下:1. 先比较169与175,169175.2. 再比较169与172,169172.3. 再比较169与171,169171.4. 再比较169与170,169170.5. 再比较169与166,169166.因此将169插入166与170之间,得到一
3、个新的有序列。解法二:有序列折半插入排序,步骤如下:1.选择中间位置的数据165,2. 将169与165比较,169165,所以169应排在165的右边。3. 取166,170,171,172,175的中间位置171.4. 将169与171比较,169171,所以169应排在171的左边.5. 取166,170中间位置166.6. 将166与169比较,169166,而169170,所以169应插在166与170之间。点评:有序列直接插入排序,要把需插入的数据与有序列中的数据依次比较,直到找到其插入的位置,比较的次数较多;折半插入排序法比较一次就排除了数据列中一半的数据,减少了比较次数,优化了运算过程。3.有序列插入排序 主要用来解决无序列的排序问题
- 温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。