高中数学 第1部分 第二章 §11.2排序问题与算法的多样性配套课件 北师大版必修3.ppt

第二章算法初步 1算法的基本思想 理解教材新知 应用创新演练 考点一 把握热点考向 考点二 1 2排序问题与算法的多样性 1 2排序问题与算法的多样性 由于人类具有主观能动性 将数据a插入到有序列 a1 a2 an 中时 能很快找到适当的位置 而计算机解决此类问题时 其解决方式不同 计算机每次只能比较两个数据的大小 不能直接 看 出应插到有序列 a1 a2 an 的哪个位置 因此要想用计算机解决排序问题必须要设计算法 使得每次仅比较两个数的大小 问题 若将3插入到有序列 3 2 2 4 7 中 排序方法有几种 提示 有两种 1 排序为了便于查询和检索 常常根据某种要求把被查询的对象用表示出来 并把按大小排列 是信息处理中一项基本的工作 通常称为排序 2 排序的方法 1 排序法 2 排序法 数字 或者符号 数字 有序列直接插入 折半插入 1 有序列直接插入排序法蕴涵的算法思想 有序列直接插入法主要是通过逐一比较 通过有限次的 操作 将某一个数据插入原有序列的一种算法 它主要包含以下两步 对于一个有序列 a1 a2 a3 an 欲将新数据a插入到有序列中 形成新的有序列 将数据a与原有序列中的数据从右到左依次进行比较 直到发现某一数据ai 使得ai a 把a插入到ai的右边 如果数据a小于原有序列中的所有数据 则将a插入到原序列的最左边 2 有序列折半插入排序法蕴涵的算法思想及插入的方法和步骤 折半插入排序的基本思想与二分法的思想一致 即逐步缩小所要比较的数据的范围 直到确定出所要插入的数据的位置为止 插入的方法如下 先将新数据与有序列中 中间位置 的数据进行比较 若有序列有2n 1个数据 则 中间位置 的数据指的是第n 1个数 若有序列有2n个数据 则 中间位置 的数据指的是第n个数 如果新数据小于 中间位置 的数据 则新数据插入的位置应该在靠左边的一半 如果新数据等于 中间位置 的数据 则将新数据插入到 中间位置 的数据的右边 如果新数据大于 中间位置 的数据 则新数据插入的位置应该在靠右边的一半 也就是说 一次比较就排除了数据列中一半的位置 反复进行这种比较直到确定新数据的位置 像这样的插入排序方法就称为折半插入排序方法 例1 将 4插入有序列 8 3 0 2 6 中 分别用直接插入排序法和折半插入排序法写出算法 思路点拨 1 利用直接插入排序法 只要按从右到左的顺序将 4逐个与有序列中数据进行比较即可 2 利用折半插入排序法 应找到中间位置a3 0与 4进行比较 然后把剩下数据中间位置的数据依次与 4比较 直到找到 4的位置 精解详析 法一 直接插入排序法 1 4与6比较 由于 4 8 则 4在 8的右边 则 4在 8与 3之间 6 得新的有序列 8 4 3 0 2 6 法二 折半插入排序法 1 4与0比较 由于 4 8 则 4在 8的右边 3 4与 3比较 由于 4 3 则 4在 3的左边 故 4在 8与 3之间 4 得新的有序列 8 4 3 0 2 6 一点通 两种算法的共同点是每次将新数据与有序列中的数据进行比较 不同点是直接插入排序法总是将数据a与原有序列中的数据从右到左依次进行比较 而折半插入排序法总是将新数据与该有序列中的 中间位置 的数据进行比较 1 将数据6通过直接插入排序的方法插入有序列 1 3 5 7 9 11 13 中 需要作比较大小的次数为 a 3b 4c 5d 6解析 数据6依次与13 11 9 7 5比较 共作5次比较大小 答案 c 2 若用折半插入排序法将4插入到有序列 0 1 2 3 中 则第一次应与该有序列中的哪个数比较 a 0b 1c 2d 3解析 因为有序列中有2 2个数 所以应先与第2个数1进行比较 答案 b 3 请利用直接插入排序和折半插入排序的方法分别写出将数据43插入有序列 21 39 46 57 67 73 84 96 的算法 解 直接插入排序算法 将43与96比较 43 96 所以43在96的左边 将43与84比较 43 84 所以43在84的左边 将43与73比较 43 73 所以43在73的左边 将43与67比较 43 67 所以43在67的左边 将43与57比较 43 57 所以43在57的左边 将43与46比较 4339 故43在39与46之间 排序后这一有序列为 21 39 43 46 57 67 73 84 96 折半插入排序算法 共8个数 中间位置上的数是57 将43与57进行比较 43 57 43在有序列的左半部分 再将余下数据的中间位置上的数39与43进行比较 39 43 43在数据39的右边 又43 46 可得43在39与46之间 即新的有序列为 21 39 43 46 57 67 73 84 96 例2 将无序列 1 17 5 12 8 25 15 按照从小到大的顺序 用自然语言写出排序算法的步骤 思路点拨 根据无序列排序的方法操作即可 用自然语言把每步操作叙述出来即可得到算法的步骤 精解详析 1 将17插入到序列 1 中得新序列 1 17 2 将5插入到序列 1 17 中得 1 5 17 3 将12插入到序列 1 5 17 中 12 5 且12 17 应将12插入到5与17之间得序列 1 5 12 17 4 将8插入到序列 1 5 12 17 中 取序列中间数5 8 5 8在5的右侧 取序列 12 17 的中间数12 817 25应在17的右侧 插入得序列 1 5 8 12 17 25 6 将15插入到 1 5 8 12 17 25 中 取序列的中间数8 15 8 15应在8的右侧 取序列 12 17 25 的中间数17 1512 15应在12的右侧 故应将15插入到12与17之间得序列 1 5 8 12 15 17 25 一点通 对一组无序的数据列进行排序时 通常将这组无序的数据列的第一个数据看成一个有序列 将第二个数据插入到这个有序列得到一个有序列 然后 将第三个数据插入到上面的有序列中 又得到一个有序列 按照这种方法 直到将最后一个数据插入到有序列中 得到一个有序列 这样实质上就是完成了对无序的数据列排序 最后得到的有序列就是对无序的数据组排序的结果 4 将有序列 5 4 3 2 1 按照从小到大的顺序输出 需要排序的次数为 a 7b 8c 9d 10解析 1 把4插入到 5 中 得 4 5 需1次排序 2 把3插入到 4 5 中 得 3 4 5 需2次排序 3 把2插入到 3 4 5 中 得 2 3 4 5 需3次排序 4 把1插入到 2 3 4 5 中 得 1 2 3 4 5 需4次排序 故共需1 2 3 4 10次排序 答案 d 5 设计算法 将 36 6 12 24 38 46 0 排序 解 1 36 是有序列 将36与6比较 因为36 6 故得到有序列 6 36 2 将12与6 36各数进行比较 因为126 故得到有序列 6 12 36 3 将24与6 12 36各数进行比较 因为24 12 2436 故得到有序列 6 12 24 36 38 5 将46与6 12 24 36 38各数进行比较 因为46 38 故得到有序列 6 12 24 36 38 46 6 将0与6 12 24 36 38 46各数进行比较 因为0 6 故得到有序列 0 6 12 24 36 38 46 所以排序之后的结果为 0 6 12 24 36 38 46 1 对于一个无序列将其重新进行有序排列的方法 方法一 利用有序列插入排序法来解决 方法二