《算法之排序》(算法与程序设计)-王乃广

《《算法之排序》(算法与程序设计)-王乃广》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、题目：算法之排序对应标准条目：选修1:算法与程序设计（三）算法与问题解决C．查找、排序与问题解决（3）掌握使用排序算法设计程序解决问题的方法。学习目标：通过实例，掌握使用排序算法设计程序解决问题的方法。建议学时：1学时过程设计：请8位同学站成一排，每人手中持有一个标有数字的小球，依次为49,38,65,97,76,13,27,50。教师站在一旁，手中没有小球。宣布要求：在9人之间传递小球使得最终小球上的数字呈递增顺序排列，规则如下：只允许小球在相邻的两个同学间传递；每人手中至多有一个小球。给出3～5分钟的考虑时间，请同学试着描述可行的传递方案，同时由台上的同学和教师演示，其他同学可以给予补充

2、或提出其他的方案。小结：刚才我们演示的实际上是冒泡排序算法，它适用与将一组无序的数据排成指定的序列（递增或递减）。她的排序规则是：从最后一个元素开始，如果它的值小于前一个元素，则交换这两个元素的值。按同样的方法，处理前一个元素，直到第一个元素为止。（注意：交换两个元素（变量）的值需要第三个变量的参与，因为一个变量只能表示一个数据，就像我们规则中所要求的，每人手中至多一个小球。）这样就使得最小的元素排到了第一个位置，然后再从最后一个元素开始处理，使得第二小的元素排到第二个位置，……，直至所有元素按递增顺序排列。示例代码如下：（先让学生构思，然后再给出。以TruboPascal为例）constn

3、=8vara:array[1..n]ofinteger;i,j,t:integer;beginfori:=1tondoread(a[I])fori:=1ton-1doforj:=ndowntoi+1doifa[j]

4、位置，其余元素的相对位置不变。那么，在某些情况下，无需n－1次即可完成排序。如果在某次处理中没有发生相邻元素的交换，也就是所任两个相邻的元素都是前下后大，那么所有元素就是递增排列的，无需再继续处理。讨论如何把这一思路用代码实现。可得改进程序如下：constn=8;vara:array[1..n]ofinteger;i,j,t:integer;flag:boolean;beginfori:=1tondoa[i]:=i;i:=1;flag:=true;whileflagand(i

5、ginflag:=true;t:=a[j];a[j]:=a[j-1];a[j-1]:=t;end;i:=i+1;end;fori:=1tondowriteln(a[i]);end.通过变量flag检查本次处理过程中是否发生交换，以此控制是否结束处理，可以提高排序的效率。学有余力的同学可以查阅更多的排序算法http://algorithm.myrice.com/index.html