(共14张PPT)
排序算法的程序实现
经典算法介绍：
排序问题是程序设计中的典型问题之一，它有很广泛的应用，比如给你一组学生成绩，要你输出前2
0
名的成绩。这时你就要用到排序。再比如要问你中国的GDP排世界第几，你要先把各国GDP排个序，才知道中国在第几。
所谓排序就是将数组中的各元素的值按从小到大的顺序或按从大到小的顺序重新排列。
小老师介绍
分析:
假设有N个数据放在数组a中,现要把这N个数从小到大排序.
冒泡排序法的基本思想是:
第一:在a[0]到a[N-1]的范围内,依次比较两个相邻元素的值,
若a[J]>a[J+1],则交换a[J]与a[J+1],J的值取0,1,2,……,N-2;经过
这样一趟冒泡,就把这N个数中最大的数放到a[N-1]中.
第二:再对a[0]到a[N-2]的范围内再进行一趟冒泡,又将该范围内的最大值换到了a[N-2]中.
第四:如果在某趟冒泡过程中没有交换相邻的值,则说明排序已完成,可以提前结束处理.
第三:依次进行下去,最多只要进行N-1趟冒泡,就可完成排序.
现假设有8个随机数已经在数组中，开始排序
初始状态：
数组a
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
6
8
5
4
6
9
3
2
第一趟排序：
两两相邻比较：
8
5
8
4
9
3
8
6
9
2
第一趟最后结果：
9
排序算法的程序设计
第二趟冒泡排序开始：
此时的待排序元素
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
冒泡法排序
6
5
4
6
8
3
2
9
5
4
6
6
3
2
8
9
4
5
6
3
2
6
8
9
同样对待排序元素两两比较后结果为：
这是第三趟冒泡的待排序元素
接着第三趟冒泡排序结果为：
同样第四趟结果为：
2
3
4
5
6
6
8
9
4
5
3
2
6
6
8
9
3
2
4
5
6
6
8
9
4
3
2
5
6
6
8
9
第六趟结果为：
第七趟结果（最终）为：
第五趟结果为：
冒泡法排序流程图
程序整体流程：
开始
结束
输入数据
输出数据
冒泡排序
细化输入数据流程：
i
=
0
i<8
scanf(“%d”,&a[i]);
i
++
N
Y
细化输出数据流程：
i
=
0
i<8
printf(“%d”,a[i]);
i
++
N
Y
执行第i趟冒泡排序
冒泡法排序流程图
i
++
i<8-1
i
=0
Y
N
j=
0
j<8-i-1
N
Y
j
++
比较相邻两元素的值并交换
a[j]>a[j+1]
交换a[j]与
a[j+1]的值
Y
N
冒泡法排序流程图
a[j]>a[j+1]
swap=1;
交换a[j]与
a[j+1]的值
Y
N
i
++;
i<8-1
i
=0
Y
N
j<8-i-1
N
Y
j
++
swap=
0
j=
0
加
入
Swap
变
量
的
流
程
图
程
序
!(swap)
break
N
Y
冒泡法程序
main(
)
{
int
i,j,a[8],temp,swap;
clrscr(
);
for(i=0;i<8;i++)
scanf("%d",&a[i]);
for(i=0;i<8;i++)
printf("%d,",a[i]);
printf("\n");
}
{
}
注：对n个元素冒泡排序第i趟排序的待排序元素是a[0]到a[n-i-1]。这里的i表示数组的下标.
swap=1;
if
(!swap)
break;
swap=0;
if
(
a[j]
>
a[j+1]
)
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
for(j=0;j<8-i-1;j++)
for(i=0;i<8-1;i++)
swap
变量的作用
如果在某趟冒泡过程中没有交换相邻的值,则说明排序已完成,可以提前结束处理.
比如：为原始数列：8、15、27、96、32、65、78、79
这个序列用冒泡法排序，一趟之后就得到升序结果，而之后的六趟都可以不要进行。
所以，swap变量就是用来标识如果某趟排序之后已经得到最终结果，则多余的次数就无须进行。
冒泡法与选择法的比较
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
数组a
6
8
5
4
6
9
3
2
K
K
i
K
K
K
2
6
每趟选择排序是找到待排序序列中最小的元素，把它交换到待排序的最前的位置。所以，一趟只有一次交换。
i
K
K
3
8
4
5
5
6
6
9
8
总
结
1.冒泡法基本思想，通过n-1趟排序把n个待排序数
大的元素象石头一样往下沉（放在最后），小的元素
象气泡一样往上浮。
2.冒泡法的流程图
3.冒泡法程序
作业：
用程序实现排序算法并上传到班级BBS中
。排序算法的程序实现
教材：浙江教育出版社《算法与程序设计》
一
教学内容分析
本节课是浙江教育出版社《算法与程序设计》中《排序算法的程序实现》的内容。将教材第二章第3节的“冒泡排序”和第五章第3节的“排序算法的程序实现”两节合并起来学习，将理论与实践结合，以加深学生对冒泡排序算法和程序设计关系的体会。排序算法是程序设计中的重要算法，对它的学习既是对已经学过的三种程序设计结构的综合运用，又能为后续对分查找的学习作好铺垫。引领学生走进算法，揭排序算法程序实现的神秘面纱。
学习本节课，不仅会填补学生关于程序设计的认知，也会对整个排序算法建立起更丰富和例题的知识结构。因此，本课学习对于学生意义非凡。
二
学情分析
本课授课对象是高二年级学生，随着我国移动互联网的高速发展，特别是互联网+以及4G技术的广泛普及，利用移动PC端（IPAD）进行随时学习，随身学习更为便捷，并且通过《信息的获取》这一章的学习，所有学生均可以熟练使用计算机进行资料信息资源的获取。在学业水平考试中，算法与程序设计将作为选修模块被大多数学生选择，在本课之前学生已经对算法了有一定的了解，赞叹于算法解决问题的高效。但是，他们大多数同学从未有过用进行程序设计的经历，更没用IPAD进行过程序设计。对利用移动PC进行程序设计有着很强的好奇心，并且对学习计算机科学有很大的兴趣。
高中的学生喜欢动手操作、喜欢钻研、喜欢竞争。同时，学生在认知水平、思维方式以及计算机操作能力等方面表现出很大的差异。这些特点，为本节课采用动手操作、合作学习等方式奠定了基础。
三
教学目标?
知识与技能：
1.理解冒泡排序的优势，理解如何利用移动端较为规范地编写程序
2.能由此及彼，归纳冒泡排序中的数字规律，探索更有效率的冒泡排序算法
过程与方法：
1.在自主探索冒泡排序算法的过程以任务分解、小组交流、互联网搜索的方式化解难点
2.在以探究法的方式，让学生在自主探索中思考发现、归纳总结，逐步将冒泡排序方法用程序语言表达出来，最终编写程序，解决问题。
情感态度与价值观：
1.在合作与竞争中，培养参与意识和研究探索精神，强化学习程序设计的热情和动力。
2.走进程序设计，培养科学的学习态度。
四
教学重难点
重点：初步掌握冒泡排序算法，以及移动PC编写算法。
难点：对冒泡排序的理解，以及冒泡排序算法的关键循环语句的理解。
五
教学策略及设计思路
“授之以鱼”不如“授之以渔”。本节课在根据“小老师”的实际需求排序的任务驱动下，引导学生经历思考——使用互联网搜索解惑——小组合作交流——借用网络软件探索解惑的过程，亲历实施计划、完成任务、学会知识和技能的途径。
本节课采用任务驱动法，用实际任务为线索，贯穿整个教学全程，也引领学生的学习和实践。
在教学过程，更注重学习方法的指导，本节课以合作学习和自主探究等方式，引导学生以小组的形式探索新知，流程图，编写程序同时鼓励学生借助网络搜索等方式大胆猜错、实践求知。
在一节程序设计课上，不纯以VB编写程序的传统讲授为形式，结合以网络搜索和软件应用，实现一次自主探索、合作交流，引导学生对信息技术形成更丰富和深刻的认识，向提升信息素养迈进。
2．教学环境
多媒体网络教室、平板电脑、相关教学课件
六
教学过程
时间：一课时40分钟
教学过程
教学环节
教师活动
学生活动
设计意图
创设环境，导入新课
提出问题：邀请一名小老师来抛出问题，实际使用过程中一串数字如何进行排序？根据1的回答，进一步追问：满足不同需求的排序方式为什么不同呢？他们主要区别体现在哪里呢？3.提出本节课的任务——分组根据实际需求，实现一个可以进行排序的程序。4.引出本节课的课题
思考并回答老师问题跟着“小老师”提问，产生猜测。投入新课学习。
利用学生感兴趣的话题激趣，使学生整堂课都能保持积极的心态去探索新知。
学习新知，任务准备
自主探索，学生交流最常见的排序算法，冒泡排序算法的概念是什么？组织分组，提出明确的注意事项后，组织自主探究，并引导学生认识冒泡算法。组织学生使用移动互联网搜索相关的功能并完成冒泡排序算法的程序设计流程图。
认真听小组交流并思考牢记注意事项，小组合作搜索概念。在搜索相关知识之后，小组讨论，合作完成老师布置的任务。
培养学生学习的严谨性，养成良好的学习习惯。学生是学习的主体，这节课的内容很容易激发起学生的学习积极性。充分放手让学生解决问题并互相交流，让他们通过实践自主学习这部分知识，突破重点。
交流分享，展示收获
组织学生交流本组搜索到的方法，引出冒泡排序算法的流程图。2.组织学生继续深入探索，如何程序如何进行的选择？
各组分别派代表结合设计的流程图的进行讲解。在观看学生讲解的过程中，互动，学习程序设计基础知识。
发挥学生的主体作用，在交流中加深记忆，并获得学习程序设计的经验。在交流中巩固算法基础知识。活跃课堂气氛。
完成任务提升认知
教师演示模拟攒机步骤，引导学生编写程序的关键语句。为各组进行有针对性的知道，组织小组合作根据具体要求，完成程序编写。选择两个具有代表性的小组成果，组织全体学生分析、点评。对各组活动进行总结，并进一步归纳冒泡算法的相关知识。并进行算法流程图的演示，再次巩固本堂课所学。
认真观看学生演示。小组合作，在再次的探索中中，加深印象。展示成果，在自评、互评之后，对本组的作品形成新的认识。跟随教师的总结，回顾学习过程，完善知识结构。
用从实际需求出发完成程序编写的任务，整合学习所得，提升理论联系实践的能力。通过任务驱动的方式，小组合作与实践探究相结合，巩固知识，更提升学习技能。引导学生在教师的总结过程中，回顾本课所学，形成程序设计的立体思想。
布置作业巩固所学
要求学生按照自己的想法利用VB程序实现一个排序算法程序，并在班级BBS中发辫，老师及同学在课后评价以及优缺点。
记录作业要求，分构思完成策略。
通过程序实现的过程，学生已经迫不及待地写出自己的所得，更加激发他们的学习热情。提高学生的评价能力。
