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

题目：算法之排序对应标准条目：选修1:算法与程序设计（三）算法与问题解决C查找、排序与问题解决（3）掌握使用排序算法设计程序解决问题的方法。学习目标：通过实例，掌握使用排序算法设计程序解决问题的方法。建议学时：1学时过程设计：请8位同学站成一排，每人手中持有一个标有数字的小球，依次为49 , 38, 65, 97, 76, 13, 27, 50。教师站在一旁，手中没有小球。宣布要求： 在9人之间传递小球使得最终小球上的数字呈递增顺序排列，规则如下：只允许小球在相邻的两个同学间传递；每人手中至多有一个小球。给出35分钟的考虑时间，请同学试着描述可行的传递方案，同时由台上的同学和教师演示，其他同学可以给予补充或提出其他的方案。小结：刚才我们演示的实际上是冒泡排序算法，它适用与将一组无序的数据排成指定的序列（递增或递减）。她的排序规则是：从最后一个元素开始，如果它的值小于前一个元素，则交换这两个元素的值。按同样的方法，处理前一个元素，直到第一个元素为止。（注意：交换两个元素（变量）的值需要第三个变量的参与，因为一个变量只能表示一个数据，就像我们规则中所要求的，每人手中至多一个小球。）这样就使得最小的元素排到了第一个位置，然后再从最后一个元素开始处理，使得第二小的元素排到第二个位置，直至所有元素按递增顺序排列。示例代码如下：（先让学生构思，然后再给出。以Trubo Pascal为例）const n=8var a:array1.nof 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.冒泡排序也可以由前向后进行，即先把最大的元素“冒”到最后一个位置，然后再把第二大元素“冒”到倒数第二个位置，。代码由学生自行编写。深入分析：冒泡排序算法中，每从头至尾处理一次，也就是内循环执行一次，使得一个元素到达最终位置，其余元素的相对位置不变。那么，在某些情况下，无需n1次即可完成排序。如果在某次处理中没有发生相邻元素的交换，也就是所任两个相邻的元素都是前下后大，那么所有元素就是递增排列的，无需再继续处理。讨论如何把这一思路用代码实现。可得改进程序如下：const n=8;var a:array1.nof 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检查本次处理过程中是否发生交换，以此控制是