《数组应用排序》设计

《数组应用-排序》教学设计（1）教学目标：知识与技能：1、理解用一维数组解决数据排序的原理；2、掌握使用交换排序法对数组排序的编程方法。过程与方法：1、通过演示交换排序的步骤，学生掌握程序设计中排序的过程；2、通过分析交换排序中的数据的交换和比较，学生掌握排序问题的解决转换成算法和程序表示的方法。情感态度价值观：通过分析交换排序中对数据一轮轮的比较，学生养成仔细、耐心的习惯。教学重点难点：交换排序算法的要点和算法设计教学过程：一、设置任务有一项体育运动项目，它的评分要求如下：有若干个裁判；每个裁判对运动员的完成情况打分；在计算最终得分前，必须将所有裁判的分值从小到大排好。请学生设计一个程序，在获取了每个裁判打的分值后，能够自动地将这些分数从小到大排好。二、活动步骤1、问题分析这里的所有数据为各个裁判对运动员完成情况的打分。例如现在有8个裁判的打分，将这8个正数存放在数组a中：A9．0下标01234567将它们从小到大排序后数组a中的数据如下：A下标01234567排序后满足：a(0)≤a(1)≤a(2)≤a(3)≤a(4)≤a(5)≤a(6)≤a(7)。让学生先自学一段有关排序的介绍，同时思考：什么是排序？把杂乱无章的数据变为有序的数据，这一过程称为排序（sorting）。交换排序用了几重循环，每重循环的作用是什么？需要二重循环：有多少个数需要确定排序位置是外循环；确定第i个数的排序位置需和它后面的数逐个比较，是内循环；(3)交换排序中数据比较的特点是什么？第i重循环是将第i个数和第i+1个数…第n个数逐一进行比较,以确定第i小的数.（4）在交换排序中数据比较和数据交换有什么联系？通过数据比较确定是否进行数据交换。教师演示第0轮过程提问：第1轮循环和第0轮比有什么特点？学生练习：请学生写出第2轮结束后a数组中的元素。2、确定算法流程图交换排序过程的关键：从小到大排序的话，是一个双重循环，有多少个数需要确定排序位置是外循环，第i次内循环是找到一个第i小的数放入i位置。学生思考：如有M个数（1）为什么只要做M-1轮操作就够了？（2）交换排序比较两个元素大小的次数是多少次？M*(M-1)/2（3）在最不理想情况下，对M个元素排序需要做几次交换操作？M*(M-1)/2（4）如果要从大到小排序，判断应怎么写？a(i)<a(j)3、编写程序同学可以参照下面残缺的程序，根据注释，补全下划线处的空缺语句n＝7Fori=0Ton-1'第i轮Forj=i+1Ton'第j个数和第i个数比较Ifa(i)>a(j)Then'交换条件t=a(i)a(i)=a(j)a(j)=tEndIfNextjNexti4、检验程序的正确性（1）老师介绍和演示测试程序。“生成”按钮自动产生10个随机数存放在a数组中，从a(0)-a(9)。“排序”按钮激活“单步演示”和“自动演示”按钮，以开始这两个操作。“检查”按钮看结果是否已从小到大排序了。“随机测试”是自动产生数据序列并测试。（2）请同学打开c:\sort文件夹中的程序，将上面的排序程序加入到class1中的csort过程中。说明：每次数据交换后必须调用swap()过程以将数据传递到测试程序，将Callswap(a,i,j,s,ns)写在三句数据交换的语句后面即可。三、教学小结和拓展：1、教师对本堂课进行小结，交换排序的关键：定义数组a（n），数据输入到a（1）-a（n）中，外循环变量i从1ton-1，内循环变量j从i+1ton,发现a（i）>a（j）则交换。2、在排序中，影响算法性能的主要部分是循环和交换，显然，循环和交换次数越多，性能就越差。交换排序怎么样可以减少交换次数？请学生研究学习一些其它的排序方法。交换排序方法某些问题的处理过程依赖于数据的有序性。把杂乱无章的数据变为有序的数据，这一过程称为排序（sorting）。排序是计算机程序经常使用的基本算法，也是现实生活经常要用到的一种数据处理方法。在排序的过程中，比较和交换是两种基本的操作。交换法是一种典型的排序方法。它的基本思想是按照升序要求（或降序要求）依次确定a(0)、a(1)、……a(n)。在确定第i小的数a（i）是什么时，可先比较a(i)与a(i+1)，若a(i+1)小（或大），就将a(i)和a(i+1)的内容互换；然后a(i)再与a(i+2)比较，若a(i+2)小（或大），仍要互换a(i)和a(i+2)的内容；……就这样，将第i小（或大）的值一直换到a(i)处。接下来，再按照上述方法确定a(i+1)、a(i+2)……。每一轮，都是把未排序部分的最小（或大）元素换到已排序部分的相邻处。经过n-1轮操作，整个数组即按升序（或降序）排列好。除了交换排序外，还有选择排序、冒泡排序、快速排序、合并排序、计数排序和桶排序等等。每一种算法都有自己的特点，所以要根据实际情况选择排序算法。【学生练习】1、第1轮结束时a中数据776543210下标a写出第2轮结束时a中数据776543210下标a2、根据流程图填写完整程序n＝7'为了程序的通用性，用n表示数据个数Fori=0To_______'第i轮Forj=________Ton'第j个数和第i个数比较If________Then'交换条件t=a(i)a(i)=a(j)a(j)=tEndIfNextjNext