《高中数学 2.3排序问题 北师大版必修3》由会员分享，可在线阅读，更多相关《高中数学 2.3排序问题 北师大版必修3（21页珍藏版）》请在金锄头文库上搜索。
1、排序问题和插入排序排序问题和插入排序排序的定义排序的定义折半插入排序折半插入排序你会从这些书籍中查你会从这些书籍中查阅你想要的东西吗？阅你想要的东西吗？ 为了便于查询，常常需要根据要求将被查寻为了便于查询，常常需要根据要求将被查寻的对象按照一定的顺序排列，通常称为的对象按照一定的顺序排列，通常称为排序。排序。新来的同学小黄身高新来的同学小黄身高175cm，在班上是中，在班上是中等身高，因为做操的需要，体育老师要将等身高，因为做操的需要，体育老师要将他插到队中，你认为老师应该怎样做？他插到队中，你认为老师应该怎样做？teacher小黄小黄 象这样在象这样在已经按一定顺序排好的系列（已经按一定顺序
2、排好的系列（有序有序列列）中插入一个数据，我们就叫它中插入一个数据，我们就叫它有序列插入排有序列插入排序。序。 有序列直接插入排序法有序列直接插入排序：用有序列直接插入排序算法完成无序列排序问题，其基本思想非常简单，即反复使用有序列直接插入排序算法，使有序列的长度不断增加，一直到完成整个无序列的有序排列为止 一般地，对于一个有序列：a1a2a3an，欲将新数据A插入到有序列中，形成新的有序列，其做法是：将数据A与原有序列中的数据从右到左依次进行比较，直到发现某一数据ai，使得aiA，把A插入到ai的右边；如果数据A小于原有序列中的所有数据，则将A插入到原序列的最左边上面的排序算法通常称为有序列
3、直接插入排序的算法我们在一个已经排好顺序的一系列数中插入一个数据，成我们在一个已经排好顺序的一系列数中插入一个数据，成为一个新的系列，且仍按原来的规则排序。为一个新的系列，且仍按原来的规则排序。要将要将8插入到插入到1,3,5,7,9,11,13中，中，我们怎样考虑？我们怎样考虑？确定确定8在原系列中的位置，使在原系列中的位置，使8小于或等于原系列小于或等于原系列中右边的数据，大于或等于左边的数据中右边的数据，大于或等于左边的数据将这个位置空出来，将数将这个位置空出来，将数据据8插进去插进去1357911138例例1已知有一组系列已知有一组系列13,27,38,39,43,47,48,51,5
4、7,66,74，现，现要将数据要将数据52插入到数据中。插入到数据中。数据系列号12345678910 11原系列13 27 38 39 43 47 48 51 57 66 74(1)请设计算法，确定请设计算法，确定52在新数据中的位置。在新数据中的位置。(2)在确定在确定52的序列号后，请将的序列号后，请将52插入系列中插入系列中(3)请用流程图描述这个插入过程的算法请用流程图描述这个插入过程的算法方法方法1.手工插入：手工插入： 确定确定52的序号：的序号：9;把原序列中把原序列中911号的数据依次向右挪一位，空号的数据依次向右挪一位，空出出9号位置来，并插入号位置来，并插入52，得到一个
5、新序列。，得到一个新序列。方法方法2. 即从右边最后一位开始，与即从右边最后一位开始，与52比较，若比比较，若比52大就右挪，否则插入大就右挪，否则插入52. 有序列插入排序算法的另一种方法有序列插入排序算法的另一种方法v折半插入排序法折半插入排序法v请同学们参看请同学们参看P84.下段下段问题思考:对于一组无序的数据列49,38,65,97,76,13,27,49如何完 成排序工作呢?v请同学们参看P85折半插入排序折半插入排序如果如果R1.i-1 是一个按关键字有序的有序序是一个按关键字有序的有序序列，则可以列，则可以利用折半查找利用折半查找实现实现“在在R1.i-1中中查找查找Ri的的插
6、入位置插入位置”，如此实现的插入，如此实现的插入排序为排序为折半插入排序折半插入排序。折半插入排序性能分析折半插入排序性能分析v1）折半插入排序折半插入排序所需附加存储空间和所需附加存储空间和直接插直接插入排序入排序相同，从时间上来看，折半插入排序相同，从时间上来看，折半插入排序减减少了关键字的比较次数少了关键字的比较次数，但是，但是移动次数不变移动次数不变。v2）折半插入排序的时间复杂度为）折半插入排序的时间复杂度为o(n2)。v3）折半插入排序是一个）折半插入排序是一个稳定稳定的排序方法。的排序方法。折半插入排序折半插入排序待排序元素的插入位置待排序元素的插入位置mid midi 0 1
7、2 3 4 5 6 7 8 9 10581436495280586123 97 75L.rlowhighlowlow例2中国乒乓球女队原有11名队员，她们的身高由小到大分别为158,159,160,162, 163,165,166,170, 171,172,175(单位：cm)现为备战某项比赛，加入一名优秀队员，这名队员身高167 cm.请设计用折半插入排序法找出该队员在序列中的位置，并用自然语言描述算法解析：由题目可获取以下主要信息：11名队员的身高；加入一名身高167 cm的队员；用折半插入排序法找出新加入队员在序列中的位置解答本题可先确定数据个数11.找到“中间位置”的数据a6165，与
8、167进行比较，然后把剩下数据“中间位置”的数据依次与167比较，直到得到167的位置解：要将167插入有序列：158,159,160,162,163,165,166,170,171,172,175，共有11个数据列表为：首先选择有序列的“中间位置”的数据a6165，将167与a6比较，显然167165，所以167应排在a6的右边a1a2a3a4a5a6a7a8a9a10a11158 159 160 162 163 165 166 170 171 172 175再取余下数据列a7，a8，a9，a10，a11的“中间位置”的数据a9171，显然167166，所以167应在a7、的右边又16747，故52不能插入到47的左边的任何位置所以，应该排在47的右边，再将余下数据的中间位置的数据57与52比较，显然5257，因此应插到57的左边，又5152，则52插入到51的右边，57的左边，即可得到52的位置小结和作业小结和作业本次课主要介绍了：本次课主要介绍了：1.有关排序的基础知识有关排序的基础知识1 1定义定义 2 2稳定性和存储方式稳定性和存储方式3 3排序算法的评价排序算法的评价 2.直接插入排序直接插入排序3、折半插入排序、折半插入排序1 1基本思想基本思想 2 2实例模拟实例模拟 3 3算法描述算法描述4 4算法的复杂度算法的复杂度
