算法与程序设计选择排序

　　一、学情分析
　　通过上学期《算法与编程》部分的学习，学生初步了解算法及其表示、比较熟悉流程图设计；
　　本学期课程为《算法与程序设计》，对算法的理解更加深入，要求能通过visual basic实现简单算法；
　　在本课之前，学生应了解了流程图的应用，熟悉在一组数中求极值算法，对于排序及冒泡排序，学生比较熟练。
　　对于本部分，学生可能会对选择排序算法的原理理解较为困难，需要教师的引导学习。学生应当在学习过程中认真听取教师对于算法的分析，在教师指导下能解释该算法的流程图，进而实现程序。
　　二、教学目标
　　知识性目标：
　　了解排序的概念、能在现实生活中列举出关于排序的实例
　　能对照冒泡排序，解释选择排序的优势，指出选择排序的策略，找出数字之间的逻辑联系
　　有迁移应用能力，能由此及彼，归纳排序中的数字规律，探索更有效率的排序算法
　　技能性目标：
　　具有模仿水平，在教师指导下可以表达出选择排序的思想，能对流程图作出解释
　　能独立完成流程图的绘制，对选择排序的各个环节比较熟练，并能在visual basic环境中规范地编写程序
　　情感、态度、价值观目标：
　　学生在学习过程中，通过亲身经历体验选择排序的实现过程，获得对此算法的感性认识
　　利用信息技术手段，开展交流合作，把自己对此算法的心得与他人交流，培养良好的信息素养，提升热爱科学的理念
　　三、重点难点
　　重点：对选择排序原理的理解，绘制流程图，数据交换，调试程序
　　难点：分析流程图
　　四、教学策略与手段
　　把握重点，先导入问题，复习排序定义，分析冒泡中数据交换次数多的问题，指出冒泡排序法效率不高，从而引出数据交换次数较少的选择排序算法
　　在教学过程中，可通过flash演示材料，比较直观地把抽象的问题简单化，由＂流程图雏形绘制＂-＂逐步完善流程图＂-＂程序实现＂-＂调试＂的过程，让学生熟练此算法与程序实现。
　　在教学中可灵活运用小组合作、分组讨论、小组间竞赛等手段进行教学，通过发散性思维的培养，增强学生对知识的探索能力。
　　五、课前准备
　　1．学生的学习准备：对流程图的绘制方法、vb语法作巩固，对选择排序算法作预习；学生分组：4人一组
　　2．教师的教学准备：准备充分的演示材料、相关数据、相关软件安装。
　　3．教学环境的设计与布置：计算机教室
　　六、教学过程
　　简要点拨排序的概念。
　　演示已经学习过的冒泡排序flash动画。
　　[小组讨论]在冒泡排序算法中，我们知道冒泡排序是依次把数组中相邻两个数据进行比较，通过交换数据，把较小的数据逐次向上移动的算法。由于数据的移动是逐次进行的，数据交换的次数相当多。大家想想它的实质既然是将一堆数据中的最小数据移动到某个位置，有没有必要让这个数字逐个移动？比如，对于数组：4、8、3、9、6、5、11、10、2、9，如果要用冒泡法实现排序，第一遍冒泡其实是把这组数据中最小数＂2＂移动到最前边，第二遍冒泡把＂3＂逐次移到第二个位置，其它类推。它们的过程是逐次向前的，这样做很多无谓的交换。为了达到移动2到最前边的目的我们可以怎么简化这个过程？
　　[学生]直接把2最前面的数4交换，再把3与第二个位置的数8交换，其它类推
　　[教师]这个思想就是今天我们要学习的选择排序算法
　　[小组讨论]选择排序的实质是每次把一堆数据中的最小数移到某个位置，那么这样的操作在规模为n的数组中会做多少次？
　　——n-1次，因为经过n-1次操作已经确定了第1到n-1个位置的次序，第n个位置也自然可以确定。
　　[小组讨论]找出数组中的最小数用什么策略?
　　[复习巩固]可以借助一个自定义的integer型变量min，用它记录最小的一个数据的下标。
　　首先，不管实际情况如何，我们先假设数组中第1个元素为最小，于是有min=1，再把这个元素与从第2个元素开始的所有元素作比较，一旦有比d(min)更小的元素存在，则修改min变量值为新的较小元素下标。这样，在d(min)经过了从第2个元素到最后一个元素的一一比较后，所得到min应该就是第1到n个元素中的选举出来的最小元素下标了。
　　然后用类似的方法，把第2到n个元素中最小数选举出来；把第3到n个元素中最小数选举出来……
　　i 1:min 1:j 2
　　开始
　　j<n ?
　　d(j)<d(min) ?
　　min j
　　y
　　y
　　n
　　………………
　　j=j+1
　　最后把每次选举出来的结果依次输出即可实现升序排列。
　　[学生完成第1遍处理过程的流程图片断]
　　[依据流程图写出代码]
　　dim min as integer
　　dim j as integer
　　min=1
　　for j=2 to n
　　if d(j)<d(min) then min=j
　　next j
　　[小组讨论]
　　在遍历了一遍后如果发现第1-n个数中的最小数d(min)，根据选择排序的思想，需要把它与第1个数字进行交换。如何进行？
　　[请同学发言]打个比方，在厨房里有一瓶酱油、一瓶醋和一个空瓶，如何利用这个空瓶实现酱油与醋？
　　——可先把酱油倒到空瓶中，再把醋倒到原来装酱油的瓶中，然后从原来的空瓶中把酱油倒到原来装醋现在已经空的瓶中，即可实现换位。
　　[教师]大家动动脑筋，用这种思想，试试把d(1)与d(min)换位，并写出相应的代码。
　　dim temp as integer
　　temp = d(i):d(i)=d(min):d(min)=temp ’关键在于引入＂空瓶＂变量temp
　　[思考]是不是每遍历一遍后必须做这样的一次交换？
　　——不是必须的，只有当确实发现有比d(1)小的数后才交换
　　[教师]那怎么知道有没有发现比d(1)更小的数呢？
　　i 1:min 1:j 2
　　开始
　　j<n ?
　　d(j)<d(min) ?
　　min j
　　y
　　n
　　n
　　………………
　　min<>1 ?
　　temp = d(1)
　　d(1)=d(min)
　　d(min)=temp
　　y
　　j=j+1
　　——其实在遍历之前我们已经假设第1个元素最小，即min=1，所以在遍历一遍后我们只需要验证一下min=1是否还成立。成立则表明没有比第1个元素小的数，不成立则表明有比第1个元素小的数，且它的下标为min，此时要交换d(1)与d(min)。
　　[学生完善流程图及代码]
　　if min <> 1 then
　　temp = d(1):d(1)=d(min):d(min)=temp
　　end if
　　[教师]我们先前说过，对于规模为n的数组，需要遍历处理次数为n-1次，以上的流程就是这n-1次中需要重复做的事，对于重复处理的事，可以用什么结构？
　　——循环，以上的比较、交换即为循环体
　　[教师]大家试着把这个循环结构流程图画出来
　　[学生完善流程图及代码]
　　开始
　　j<n ?
　　d(j)<d(min) ?
　　min j
　　y
　　n
　　输出排序结果
　　n
　　min<>i ?
　　temp = d(i)
　　d(i)=d(min)
　　d(min)=temp
　　y
　　i<=n-1
　　i 1
　　y
　　n
　　结束
　　i=i+1
　　j=j+1
　　min=i:j=i+1
　　for i = 1 to n-1
　　min = i
　　for j = i + 1 to n
　　if d(j) < d(min) then min = j
　　next j
　　if min <> i then
　　temp = d(i):d(i) = d(min):d(min) = temp
　　end if
　　next i
　　for m = 1 to n
　　print(str(d(m)))
　　next m
　　[调试程序]
　　[扩展提高]
　　我们知道，冒泡排序的效率比较低，主要因为数据交换的次数多，那我们如何知道选择排序中数据交换的次数？
　　[学生带着问题思考并实践]
　　——可利用一个自定义integer型变量，初值0，记录数据交换次数，在程序交换数据部分令其自加1，程序结束时输出结果。
　　[完整的程序为]
　　dim i,j,min,m,cishu as integer
　　cishu=0
　　for i = 1 to n-1
　　min = i
　　for j = i + 1 to n
　　if d(j) < d(min) then min = j
　　next j
　　if min <> i then
　　temp = d(i):d(i) = d(min):d(min) = temp:cishu=cishu+1
　　end if
　　next i
　　for m = 1 to n
　　print(str(d(m)))
　　next m
　　print(str(cishu))
　　【问题研讨】
　　对于规模非常大时，计算选择排序与冒泡排序交换次数，研究时间、空间复杂度
　　利用网络、图书，发现更优秀的排序算法，并对各种算法进行效率分析