高中信息技术选修1：算法与程序设计 4.4.1 选择排序算法

主讲人:林武坚

QQ:364515313Email:linwujian@126.com信息技术普通高中选修1第四章算法及其程序实现第四章算法及其程序实现4.1用解析法设计程序4.4.1选择排序算法4.3查找算法设计4.4排序算法设计4.5递归算法与递归程序4.6问题求解综合活动4.2用穷举法设计程序4.4.1选择排序算法请两名同学在两副扑克牌A、B中找到以下指定的扑克牌，看哪位同学找的快？活动：查找我最快★情境导入（注：A扑克牌按照花色以及从小到大排序，B扑克牌已被随机打乱）15:304.4.1选择排序算法提问：为什么这位同学更快？这告诉我们什么道理？数据排序很有必要！分析：4.4.1选择排序算法提问：什么是排序呢？把一组数据根据指定的排序因子整理为特定序列称为排序。

常见排序一般分为以下两种：1.顺序排序（从小到大）2.逆序排序（从大到小）分析：★概念界定15:324.4.1选择排序算法提问：如何给数据排序呢？下面是20位同学的“信息技术课堂表现综合评价”得分，请编制程序把他们由小到大排成顺序：5，1，3，4，2，18，7，20，13，17，9，15，11，10，16，6，8，12，19，14。问题描述：“学霸”排行榜问题解决：1.分析问题★算法探索15:394.4.1选择排序算法游戏：排序我最行4.4.1选择排序算法在n（n=20）个数据中选择最小的，把它放置到第1个位置上（若有数据则对调）在剩下的n-1（n-1=19）个数据中选择最小的，把它放置到第2个位置上（若有数据则对调）在剩下的n-2（n-2=18）个数据中选择最小的，把它放置到第3个位置上（若有数据则对调）……在剩下的2（n-18=2）个数据中选择最小的，把它放置到第n-1个位置上（若有数据则对调）选择过程示意图提问：请描绘刚才游戏的排序过程？分析：选择排序法超过十种算法4.4.1选择排序算法2.设计算法选择排序法的思路：先在全部数据中找出最小的排好，再在余下数据中继续找出最小的排好，不断重复这个过程，直到只剩一个数据时为止。提问：以前面五个数据5,1,3,4,2为例，请按照以上选择排序的方法将数据从小到大排序，分析写出每遍选择后的结果。4.4.1选择排序算法分析：12345初始1遍后2遍后3遍后4遍后编号513421534212345123451234512345初始1遍后2遍后3遍后4遍后编号||n-1i=i=i=i=n||1525513424.4.1选择排序算法提问：每一遍中怎样找出最小的？开始i<=n-1结束否i=1是i=i+1在第i到n个数据中选择最小的，把它与排在第i个位置的数据对调选择排序算法的简化算法流程图在第i到n个数据中选择最小的，把它与排在第i个位置的数据对调4.4.1选择排序算法游戏：寻找“最young小鲜肉”？

请五位同学上台参与游戏活动，根据指定游戏规则（老师提示），找出年龄（老师给每位同学都假定了一个年龄）最小的同学，感受其中蕴含的算法思想。15:454.4.1选择排序算法12345分析：minmjjminmijj15.515.115.315.415.2n4.4.1选择排序算法找到最小值的思路：可先假定当前第一个数是最小的数min，标记之m。接着将假定最小的数min与后面数d(j)(j=i+1)依次比较。若发现比它小的，则更改为假定这个新的数d(j)为最小的数min，更改标记m；若没发现，则不更改。以此类推j=j+1。比较结束之后，则标记的数m就是最小的数min。4.4.1选择排序算法123451次后51342编号5342513422minmji12345编号minmji第1遍2次后534251342212345编号minmji第1遍初始第1遍分析：minmjjnnn15:524.4.1选择排序算法3次后534251342212345编号minmji第1遍4次后54251342212345编号minmji第1遍交换后534215342212345编号i第1遍51nnnj第i—第n个数中求最小值的算法流程图4.4.1选择排序算法开始结束否min=d(i),m=i是否j=i+1d(j)<minj<=nj=j+1是min=d(j),m=jk=d(i),d(i)=d(m),d(m)=k4.4.1选择排序算法123451次后51342编号5342513422minmji12345编号minmji第1遍2次后534251342212345编号minmji第1遍初始第1遍分析：minmjjnnn4.4.1选择排序算法3次后534251342212345编号minmji第1遍4次后54251342212345编号minmji第1遍交换后534215342212345编号i第1遍51nnnj4.4.1选择排序算法初始534215342212345编号minmji第2遍1次后534215342212345编号minmji第2遍2次后534215342212345编号minmji第2遍nnnjjminmminm4.4.1选择排序算法3次后5421534212345编号minmji第2遍交换后534212342512345编号minmji第2遍初始534212342512345编号minmji第3遍nnn254.4.1选择排序算法1次后534212342512345编号minmji第3遍2次后53212342512345编号minmji第3遍交换后534212342512345编号i第3遍nnnjj4.4.1选择排序算法初始534212342512345编号minmji第4遍1次后53412342512345编号minmji第4遍交换后534212342512345编号i第4遍nnn4.4.1选择排序算法开始i<=n-1结束否i=1min=d(i),m=i是否j=i+1是否d(j)<minj<=ni=i+1j=j+1是min=d(j),m=jk=d(i),d(i)=d(m),d(m)=k选择排序算法的完整算法流程图4.4.1选择排序算法3.编写程序界面设计如下：任务：找到学习资源文件夹中“工程1.vbp”文件，请将程序中的问号处修改完整，实现数据从小到大排序。16:054.4.1选择排序算法PrivateSubForm_Click()

Dimd(100)AsSinglen=Val(InputBox("请输入数据的总数量"))Fori=1Tond(i)=Val(InputBox("请输入第"&i&"个数据"))Nexti代码编写如下：4.4.1选择排序算法Fori=

To

Min=d(i):m=iForj=

To

Ifd(j)<MinThenMin=d(j):m=jNextjk=d(i):d(i)=d(m):d(m)=kNextiFori=1TonPrintd(i),:IfiMod5=0ThenPrintNextiEndSub1n-1ni+1????4.4.1选择