1.2排序问题与算法的多样性
图片预览
文档简介
课件14张PPT。1高中数学必修3第二章算法初步排序问题与算法的多样性西安市东方中学
薛冠峰2排序问题和插入排序排序的定义折半插入排序3你会从这些书籍中查阅你想要的东西吗？ 为了便于查询，常常需要根据要求将被查寻的对象按照一定的顺序排列，通常称为排序。4新来的同学小黄身高175cm，在班上是中等身高，因为做操的需要，体育老师要将他插到队中，你认为老师应该怎样做？teacher小黄 象这样在已经按一定顺序排好的系列（有序列）中插入一个数据，我们就叫它有序列插入排序。 5有序列插入排序我们在一个已经排好顺序的一系列数中插入一个数据，成为一个新的系列，且仍按原来的规则排序。要将8插入到{1,3,5,7,9,11,13}中，我们怎样考虑？确定8在原系列中的位置，使8小于或等于原系列中右边的数据，大于或等于左边的数据将这个位置空出来，将数据8插进去86例题分析例1已知有一组系列{13,27,38,39,43,47,48,51,57,66,74}，现要将数据52插入到数据中。(1)请设计算法，确定52在新数据中的位置。(2)在确定52的序列号后，请将52插入系列中(3)请用流程图描述这个插入过程的算法7方法1.手工插入： ①确定52的序号：9;②把原序列中9～11号的数据依次向右挪一位，空出9号位置来，并插入52，得到一个新序列。方法2.
即从右边最后一位开始，与52比较，若比52大就右挪，否则插入52.
8有序列插入排序算法的另一种方法折半插入排序法
请同学们参看P84.下段
9问题思考:对于一组无序的数据列{49,38,65,97,76,13,27,49}如何完 成排序工作呢?请同学们参看P8510折半插入排序如果R[1..i-1] 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。11折半插入排序性能分析1）折半插入排序所需附加存储空间和直接插入排序相同，从时间上来看，折半插入排序减少了关键字的比较次数，但是移动次数不变。
2）折半插入排序的时间复杂度为o(n2)。
3）折半插入排序是一个稳定的排序方法。12折半插入排序待排序元素的插入位置 0 1 2 3 4 5 6 7 8 9 105814364952805861239775L.r13小结和作业本次课主要介绍了：1.有关排序的基础知识1．定义 2．稳定性和存储方式3．排序算法的评价 2.直接插入排序3、折半插入排序1．基本思想 2．实例模拟 3．算法描述4．算法的复杂度 14作业：10.1(1，2)，10.23，10.24 教学反思：
薛冠峰2排序问题和插入排序排序的定义折半插入排序3你会从这些书籍中查阅你想要的东西吗？ 为了便于查询，常常需要根据要求将被查寻的对象按照一定的顺序排列，通常称为排序。4新来的同学小黄身高175cm，在班上是中等身高，因为做操的需要，体育老师要将他插到队中，你认为老师应该怎样做？teacher小黄 象这样在已经按一定顺序排好的系列（有序列）中插入一个数据，我们就叫它有序列插入排序。 5有序列插入排序我们在一个已经排好顺序的一系列数中插入一个数据，成为一个新的系列，且仍按原来的规则排序。要将8插入到{1,3,5,7,9,11,13}中，我们怎样考虑？确定8在原系列中的位置，使8小于或等于原系列中右边的数据，大于或等于左边的数据将这个位置空出来，将数据8插进去86例题分析例1已知有一组系列{13,27,38,39,43,47,48,51,57,66,74}，现要将数据52插入到数据中。(1)请设计算法，确定52在新数据中的位置。(2)在确定52的序列号后，请将52插入系列中(3)请用流程图描述这个插入过程的算法7方法1.手工插入： ①确定52的序号：9;②把原序列中9～11号的数据依次向右挪一位，空出9号位置来，并插入52，得到一个新序列。方法2.
即从右边最后一位开始，与52比较，若比52大就右挪，否则插入52.
8有序列插入排序算法的另一种方法折半插入排序法
请同学们参看P84.下段
9问题思考:对于一组无序的数据列{49,38,65,97,76,13,27,49}如何完 成排序工作呢?请同学们参看P8510折半插入排序如果R[1..i-1] 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。11折半插入排序性能分析1）折半插入排序所需附加存储空间和直接插入排序相同，从时间上来看，折半插入排序减少了关键字的比较次数，但是移动次数不变。
2）折半插入排序的时间复杂度为o(n2)。
3）折半插入排序是一个稳定的排序方法。12折半插入排序待排序元素的插入位置 0 1 2 3 4 5 6 7 8 9 105814364952805861239775L.r13小结和作业本次课主要介绍了：1.有关排序的基础知识1．定义 2．稳定性和存储方式3．排序算法的评价 2.直接插入排序3、折半插入排序1．基本思想 2．实例模拟 3．算法描述4．算法的复杂度 14作业：10.1(1，2)，10.23，10.24 教学反思：