《《算法之排序》(算法与程序设计)-王乃广》由会员分享，可在线阅读，更多相关《《算法之排序》(算法与程序设计)-王乃广（4页珍藏版）》请在金锄头文库上搜索。
1、题目：算法之排序 对应标准条目： 选修1:算法与程序设计 （三）算法与问题解决 C查找、排序与问题解决 （3）掌握使用排序算法设计程序解决问题的方法。 学习目标： 通过实例，掌握使用排序算法设计程序解决问题的方法。 建议学时：1学时 过程设计： 请8位同学站成一排，每人手中持有一个标有数字的小球，依次为49 , 38, 65, 97, 76, 13, 27, 50。教师站在一旁，手中没有小球。 宣布要求： 在9人之间传递小球使得最终小球上的数字呈递增顺序排列，规则如下： 只允许小球在相邻的两个同学间传递； 每人手中至多有一个小球。 给出35分钟的考虑时间，请同学试着描述可行的传递方案，同时由台
2、上的同学和教师演示，其他同学可以给予补充或提出其他的方案。 小结：刚才我们演示的实际上是冒泡排序算法，它适用与将一组无序的数据排成指定的序列（递增或递减）。她的排序规则是： 从最后一个元素开始，如果它的值小于前一个元素，则交换这两个元素的值。按同样的方法，处理前一个元素，直到第一个元素为止。（注意：交换两个元素（变量）的值需要第三个变量的参与，因为一个变量只能表示一个数据，就像我们规则中所要求的，每人手中至多一个小球。）这样就使得最小的元素排到了第一个位置，然后再从最后一个元素开始处理，使得第二小的元素排到第二个位置，直至所有元素按递增顺序排列。示例代码如下：（先让学生构思，然后再给出。以Tr
3、ubo Pascal为例） const n=8 var a:array1nof integer; i,j,t:integer; begin for i:=1 to n do read(aI) for i:=1 to n-1 do for j:=n downto i+1 do if ajaj-1 then begin t:=aj; aj:=aj-1; aj-1:=t; end; for i:=1 to n do writeln(ai); end. 冒泡排序也可以由前向后进行，即先把最大的元素“冒”到最后一个位置，然后再把第二大元素“冒”到倒数第二个位置，。代码由学生自行编写。 深入分析：冒泡排序
4、算法中，每从头至尾处理一次，也就是内循环执行一次，使得一个元素到达最终位置，其余元素的相对位置不变。那么，在某些情况下，无需n1次即可完成排序。如果在某次处理中没有发生相邻元素的交换，也就是所任两个相邻的元素都是前下后大，那么所有元素就是递增排列的，无需再继续处理。讨论如何把这一思路用代码实现。可得改进程序如下： const n=8; var a:array1nof integer; i,j,t:integer; flag:boolean; begin for i:=1 to n do ai:=i; i:=1; flag:=true; while flag and (in) do begin flag:=false; for j:=n downto i+1 do if ajaj-1 then begin flag:=true; t:=aj; aj:=aj-1; aj-1:=t; end; i:=i+1; end; for i:=1 to n do writeln(ai); end. 通过变量flag检查本次处理过程中是否发生交换，以此控制是否结束处理，可以提高排序的效率。 学有余力的同学可以查阅更多的排序算法 http:/
