高中信息技术 人教版选修1 4.5排序(共16张PPT)

排序 排 序： 将一组无序输入的关键字变成一组有序输出的过程！ 1 为什么 要排序呢？ 2 计算机 如何进行排序的呢 冒泡算法 _______________________________________ 1）原理：是一种反复扫描整个序列，一次比较两个相邻元素，如果他们的顺序错误就把他们交换过来。 两两比较,交换? 冒泡算法简单演示 列队排序游戏（升序） 游戏 规则 S1、共需要7位同学 5位同学站成一排充当“执行员” 1位同学充当“大脑” 1位同学充当“记录员” S2、每次2位相邻同学出列 S3、比较后，“大脑”决定是否交换 如若交换，两位同学交换位置 “记录员”记录比较次数、交换次数 S4、站回队列,依次类推… 冒泡算法的性质 N个数共加工多少次才能排好呢？ 第1次加工，确定第1个最值； 第2次加工，确定第2个最值； …. 第N-1次加工，确定第N-1个最值。 结论1： N个数共需要加工N-1次才能排好序！ 5个数共加工多少次才排好序呢？ 4次 N个数共比较多少次才排好序呢？ 第1次加工，需要N-1次比较； 第2次加工，需要N-2次比较； …. 第N-2次加工，需要2次比较； 第N-1次加工，需要1次比较。 共需1+2+ …(N-2)+(N-1)=N*(N-1)/2 结论2： N个数共需比较N*(N-1)/2次才能排好序！ 5个数共比较多少次才排好序呢？ 10次 结论3： N个数排序交换的次数[0,N*(N-1)/2]！ 计算机能一步实现这样的交换吗？ 雪碧和可乐的互换 有两个杯子A和B，A杯装有雪碧，B杯装有可乐，问如何把两个杯子中的饮料互换。 a 雪碧 b 可乐 t 代码： t=a a=b b=t 数组 Dim R(1to 5) As Integer 8 R(5) 30 R(4) 2 R(3) 50 R(2) 10 R(1) 数据 数组 8 R(5) 30 R(4) 2 R(3) 50 R(2) 10 R(1) 数据 数组 t 8<30,位置交换 8 8 R(5) 30 R(4) 2 R(3) 50 R(2) 10 R(1) 数据 数组 30 8 30 R(5) 8 R(4) 2 R(3) 50 R(2) 10 R(1) 数据 数组