高中数学 2.3排序问题 北师大版必修3.ppt

2 3排序问题 北师大版高中数学必修3第二章 算法初步 排序问题和插入排序 排序的定义 折半插入排序 你会从这些书籍中查阅你想要的东西吗 为了便于查询 常常需要根据要求将被查寻的对象按照一定的顺序排列 通常称为排序 新来的同学小黄身高175cm 在班上是中等身高 因为做操的需要 体育老师要将他插到队中 你认为老师应该怎样做 teacher 小黄 象这样在已经按一定顺序排好的系列 有序列 中插入一个数据 我们就叫它有序列插入排序 有序列直接插入排序法有序列直接插入排序 用有序列直接插入排序算法完成无序列排序问题 其基本思想非常简单 即反复使用有序列直接插入排序算法 使有序列的长度不断增加 一直到完成整个无序列的有序排列为止 一般地 对于一个有序列 a1 a2 a3 an 欲将新数据a插入到有序列中 形成新的有序列 其做法是 将数据a与原有序列中的数据从右到左依次进行比较 直到发现某一数据ai 使得ai a 把a插入到ai的右边 如果数据a小于原有序列中的所有数据 则将a插入到原序列的最左边 上面的排序算法通常称为有序列直接插入排序的算法 有序列插入排序 我们在一个已经排好顺序的一系列数中插入一个数据 成为一个新的系列 且仍按原来的规则排序 要将8插入到 1 3 5 7 9 11 13 中 我们怎样考虑 确定8在原系列中的位置 使8小于或等于原系列中右边的数据 大于或等于左边的数据 将这个位置空出来 将数据8插进去 8 例题分析 例1已知有一组系列 13 27 38 39 43 47 48 51 57 66 74 现要将数据52插入到数据中 1 请设计算法 确定52在新数据中的位置 2 在确定52的序列号后 请将52插入系列中 3 请用流程图描述这个插入过程的算法 方法1 手工插入 确定52的序号 9 把原序列中9 11号的数据依次向右挪一位 空出9号位置来 并插入52 得到一个新序列 方法2 即从右边最后一位开始 与52比较 若比52大就右挪 否则插入52 有序列插入排序算法的另一种方法 折半插入排序法请同学们参看p84 下段 问题思考 对于一组无序的数据列 49 38 65 97 76 13 27 49 如何完成排序工作呢 请同学们参看p85 折半插入排序 如果r 1 i 1 是一个按关键字有序的有序序列 则可以利用折半查找实现 在r 1 i 1 中查找r i 的插入位置 如此实现的插入排序为折半插入排序 折半插入排序性能分析 1 折半插入排序所需附加存储空间和直接插入排序相同 从时间上来看 折半插入排序减少了关键字的比较次数 但是移动次数不变 2 折半插入排序的时间复杂度为o n2 3 折半插入排序是一个稳定的排序方法 折半插入排序 待排序元素的插入位置 012345678910 58 14 36 49 52 80 58 61 23 97 75 l r 例2中国乒乓球女队原有11名队员 她们的身高由小到大分别为158 159 160 162 163 165 166 170 171 172 175 单位 cm 现为备战某项比赛 加入一名优秀队员 这名队员身高167cm 请设计用折半插入排序法找出该队员在序列中的位置 并用自然语言描述算法 解析 由题目可获取以下主要信息 11名队员的身高 加入一名身高167cm的队员 用折半插入排序法找出新加入队员在序列中的位置 解答本题可先确定数据个数11 找到 中间位置 的数据a6 165 与167进行比较 然后把剩下数据 中间位置 的数据依次与167比较 直到得到167的位置 解 要将167插入有序列 158 159 160 162 163 165 166 170 171 172 175 共有11个数据 列表为 首先选择有序列的 中间位置 的数据a6 165 将167与a6比较 显然167 165 所以167应排在a6的右边 再取余下数据列 a7 a8 a9 a10 a11 的 中间位置 的数据a9 171 显然167166 所以167应在a7 的右边 又167 a8 所以167应插在a7与a8之间 评析 用折半插入排序法向有序列中插入新数据时 首先确定原有序列中数据的个数是偶数2n还是奇数2n 1 若为偶数 则 中间位置 的数据是第n个数据 若为奇数 则 中间位置 的数据为第n 1个数据 然后将新数据与 中间位置 的数据比较 若新数据大于 中间位置 的数据 则在右半边进行下一步骤 若新数据小于 中间位置 的数据 则在左半边进行下一步骤 依次类推 就可以确定新数据在序列中的位置 变式练习将52插入有序列 13 27 38 39 43 47 48 51 57 66 74 82 中 构成一个新的有序列 解 首先选择有序列中具有中间位置序号的数据47 将52与47进行比较 显然52 47 故52不能插入到47的左边的任何位置 所以 应该排在47的右边 再将余下数据的中间位置的数据57与52比较 显然52 57 因此应插到57的左边 又51 52 则52插入到51的右边 57的左边