《选择排序的算法及程序实现.doc》由会员分享，可在线阅读，更多相关《选择排序的算法及程序实现.doc（8页珍藏版）》请在金锄头文库上搜索。
1、选择排序的算法及程序实现 浙江省慈溪中学 施迪央教学分析：本节课是浙江教育出版社出版的普通高中课程标准实验教科书算法与程序设计第二第3节以及第五章第3节的部分教学内容。经过冒泡排序的学习，学生对计算机排序有了一定的认识。选择排序是对冒泡排序的改进。特别是对键盘输入的一批数据进行选择热排序，无非是冒泡的代码改为选择代码，所以学习起来相对轻松了。关于选择排序的算法及程序实现我安排了3个课时，本案例是在教室内完成的2节随堂课，第3课时安排学生任选下面一个主题进行上机实践，主题一：对键盘输入的一批数据进行选择排序，主题二：对计算机自动生成的一批数据进行选择排序。教学目标：1、知识与技能：了解选择排序的
2、概念及特点掌握选择排序算法的原理初步掌握选择排序的程序实现选择排序与冒泡排序的异同。2、过程与方法理解选择排序的分析过程，并初步掌握用选择排序算法来设计解决简单的排序问题3、情感态度与价值观通过选择排序过程的体验，培养学生使用科学方法解决问题的能力使学生深入理解计算机的工作原理，激发了学生学习程序兴趣。教学重点：选择排序算法的原理教学难点：分析选择排序的实现过程教学策略： 讲授法与探究法。教师讲授、学生听讲，教师提问、学生动脑，层层深入，步步为营，一切水到渠成。教学准备：编写好手动输入一系列的数据的选择排序的程序编写好计算机自动生成数据的选择排序的程序 课堂中使用的教学课件教学过程：一、选择排
3、序的算法思想及程序实现1、关于选择排序的思想问题一：什么是选择排序（selection sort）选择排序是对冒泡排序算法的改进，在参加排序的所有数组元素中找出最小数据的元素，使它与第一个元素中的数据相互交换位置。然后再在余下的元素中找出最小数据的元素，与第二个元素中的数据相互交换位置，以此类推，直到所有元素成为一个有序的序列。此方法中交换的次数比冒泡排序少，具有较高的效率。第一遍加工：第一个元素a(1) 最小数据a(k) 交换位置第二遍加工：第二个元素a(2) 最小数据a(k) 交换位置问题二：交换位置有条件吗？条件是什么？ 有第一遍k1，第二遍k2，第三遍，k3问题三：选择排序交换的次数最
4、多是几次？最多是排序的遍数，若n个数据，交换的次数最多是n-1遍，即交换的次数要比冒泡排序少。2、提出待排序的任务并作初步的加工例子：有下面一组数据，3，8，1，7，用选择排序法实现从小到大的排序这4个数据分别用数组变量a的4个数组元素a(1)、a(2)、a(3)、a(4)来存储变量 a(1) a(2) a(3) a(4) 初始 3 8 1 7结果 1 3 7 8问题一：你能根据选择排序的概念来写出每遍加工的结果吗？变量 a(1) a(2) a(3) a(4) 初始 3 8 1 7第一遍 1 8 3 7第二遍 1 3 8 7第三遍 1 3 7 8问题二：4个数据选择排序需要通过几遍加工？n个数
5、据呢？3遍，n-1遍，与冒泡排序相同问题三：请用语言来描述一下计算机实现选择排序的思路吗？第一遍加工：找到4个数据中(即待排序区域a(1)a(4)的最小数1，与第一个位置的数据3发生位置交换第二遍加工：找到3个数据中(即待排序区域a(2)a(4)的最小数3，与第二个位置的数据8发生位置交换第三遍加工：找到2个数据中(即待排序区域a(3)a(4)的最小数7，与第三个位置的数据8发生位置交换问题四：在什么情况下不发生位置交换？在待排序区域中的第一个位置的数据就是要找的最小数，不用交换3、 选择排序算法及程序初步实现（1）第一遍加工： 变量 a(1) a(2) a(3) a(4) 初始 3 8 1
6、7第一遍 1 8 3 7分析如下： i=1(用变量i表示第一遍处理，也表示第一个数据元素) 在第1至第4个数组元素中找最小数据 (最小数据的下标用变量k表达,首先默认最小数据a(k)为第一个数据，然后余下的3个数据分别跟a(k)比较，如果有比a(k)小的话，k重新赋值为最小数据的下标) 如果找到的最小数据下标k不是1(i)的话，那么与第一个数据元素发生交换(如果ki(i=1)，则a(k)与a(i)交换) 结果(第一个位置中的数据值最小，a(2)a(4)为无序区域)根据分析过程，写出第一遍加工代码：i=1 k=1 for j=2 to 4 if a(j)a(k) then k=jnext jif
7、 ki then temp=a(k):a(k)=a(i):a(i)=tempEnd if（2）第二遍加工：分析如下： i=2(用变量i表示第二遍处理,也表示第二个数据元素) 在第2至第4个数组元素中找最小数据 (首先默认最小数据a(k)为第二个数据a(2)，然后余下的2个数据分别跟a(k)比较，如果有比a(k)小的话，k重新赋值为最小数据的下标) 找到的最小数据下标k如果不是2(i)的话,那么与第二个数据元素发生交换(如果ki(i=2),则a(k)与a(i)交换) 结果(第二个位置中的数据值次小,a(3)a(4)为无序区域)根据分析过程，写出第二遍加工代码：i=2k=2 for j=3 to
8、4 if a(j)a(k) then k=jnext jif ki then temp=a(k):a(k)=a(1):a(1)=tempEnd if问题一：变量i、j、k有什么区别和联系？共同点：三个变量都是数组a的下标变量，即都表示某一数组元素不同点：i另外表示数据的某遍处理，i=1表示第一遍处理，i=2表示第二遍处理 K另外表示最小数据的下标（3）第三遍加工：根据前两遍加工的分析，写出第三遍加工代码，如下：i=3k=3for j=4 to 4 if a(j)a(k) then k=jnext jif ki then temp=a(k):a(k)=a(i):a(i)=tempEnd if（4
9、）4个数据进行选择排序的程序代码For i=1 to 3k=ifor j=i+1 to 4 if a(j)a(k) then k=jnext jif ki then temp=a(k):a(k)=a(i):a(i)=tempEnd ifNext i4、n个数据进行选择排序的通用代码，用双重循环解决For i=1 to n-1k=ifor j=k +1 to n if a(j)a(k) then k=jnext jif ki then temp=a(k):a(k)=a(i):a(i)=tempEnd ifNext i问题一：双重循环中，外、内循环的意义各是什么？外循环是加工的遍数，n个数据需要加
10、工n-1遍 在For iNext i中间部分，是每一遍的具体加工过程5、 演示选择排序算法.swf，观察流程图，体验流程的执行过程，并请学生用语言表达程序运行过程二、选择排序跟冒泡排序的异同1、相同点：处理遍数相同:n个数据需处理n-1遍每一遍都是找最小数2、不同点：找最小数的方法不同冒泡，每一遍排序，总是从最末位置的数据与前面相邻位置的数据发生比较，如果小于前面位置的数据，则交换；重复这一过程，直到处理完待排序数据区域中的最前面两个位置的数据为止；选择，每一遍排序，总是在待排序的无序区域中找出最小数据的元素，使它与该遍排序对应的元素相互交换位置交换的次数不同选择排序交换的次数排序的遍数三、例
11、子，对键盘输入的一批数据进行选择排序1、关于程序的界面问题一：界面与冒泡排序的界面雷同吗？（是的）问题二：根据界面所示，请说出程序的运行过程在黄色文本框内输入数据后，按回车键，在左边列表框list1内显示输入的数据，依次输入一批数据，然后单击“选择排序”按钮，在列表框list2中显示排好序的一列数据问题三：在哪几个对象上发生哪些事件？文本框text1的Keypress事件和命令按钮command1的click事件2、编写事件的代码问题一：请尝试编写text1_keypress（）事件的代码(参考计算并联电路的总电阻)Sub Text1_KeyPress(KeyAscii As Integer)
12、 If KeyAscii = 13 Then c=c+1 a(c) = Val(Text1.Text) List1.AddItem a(c) Text1.Text = : Text1.SetFocusEnd IfEnd Sub问题二：当在text1中用键盘输入回车键后，计算机做些什么内容？ 计数（c=c+1） 给数组变量a赋值 数组变量的值在list1中显示 text1清空，并把光标聚焦在text1中问题三：数组变量a和变量c需要在text1_keypress()事件中定义吗？不用，作全局性变量处理，在模块外添加如下两行：Dim a(1 to 128) as integer Dim c As
13、Integer 问题四：如果要手动输入50个待排序的数据，需要执行text1_keypress()事件几遍？50遍问题五：请尝试编写command1_click()事件Sub Command1_Click()For i = 1 To c 1k=i For j = i+1 To c If a(J) a(k) Then k=j Next JIf kI then TEMP = a(J)：a(J) = a(k)：a(k) = TEMPEnd ifNext iFor i = 1 To cList2.AddItem a(I)Next iEnd Sub问题六：command1_click()事件实现哪几项功能？两项功能：一项是实现选择排序，一项是把已排好序的数组a输出（用for循环实现）教师演示事先编好的程序，让学生观察并体验程序的执行过程关于这些问题的提出与解决，基本与冒泡排序一致3、关于程序的升降序功能问题一：如果要实现升降序的功能，界面与代码如何修改？界面修改：添加一
