3.4.1冒泡法排序算法

1、教科版算法与程序设计(选修） 唐县职业技术教育中心 主讲教师：甄兰霞,高中信息技术,3.4 对数据进行排序,时 间 先 后 排 序,价 格 排 序,排序：,排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“按关键字有序”的记录序列。,如何按照身高从矮到高排序呢？,（1）依次比较相邻的两个数据，如果发现它们的次序相反，就进行交换，直到没有反序为止。 （2）又称起泡排序，在整个排序过程中，关键字小的就像气泡一样往上升，每一轮比较后，均有一个当前最大的记录移到最后。,冒泡排序基本原理：,例：将五个卡通人物的身高放入一维数组A中，要求利用冒泡排序法将人物身高按从小到大的顺序进行

2、排序。,冒泡排序的过程,a(1)高于a(2)，交换,a(2)低于a(3)，不交换,a(3)高于a(4)，交换,a(4)高于a(5)，交换,第一轮排序，一共经过了多少次比较？,第一轮排序：,a(5),a(4),a(3),a(2),a(1),对比原数据经过第一轮排序，实现了什么目的？,第二轮排序：,a(5),a(4),a(3),a(2),a(1),a(1)低于a(2)，不交换,a(2)高于a(3)，交换,a(3)高于a(4)，交换,经过第二轮排序，个子第二高的卡通人排到了倒数第二位。,第三轮排序：,a(5),a(4),a(3),a(2),a(1),a(1)高于a(2)，交换,a(2)低于a(3)，

3、不交换,经过第三轮排序，个子第三高的卡通人排到了倒数第三位。,第四轮排序：,a(5),a(4),a(3),a(2),a(1),a(1)低于a(2)，不交换,这样，经过第四轮排序，第四高的卡通人就排到了倒数第四位，那么，剩下的一个卡通人肯定就是最矮的。,冒泡排序过程数字化： 用冒泡法对5个数据排序（按从小到大的顺序）,第 一 轮 比 较,原始数据,A(1),A(2),A(3),A(4),A(5),162,155,182,164,157,第一次,164,157,182,164,157,155,182,164,157,162,155,182,164,157,162,155,182,164,157,1

4、62,155,182,162,155,157,182,162,155,164,157,182,162,155,164,157,182,162,155,164,157,182,162,155,164,157,182,162,155,164,157,182,162,155,164,157,182,162,155,162,155,182,164,157,第二次,162,155,182,164,157,第三次,162,155,182,164,157,第四次,A(1)A(2) 交换,A(2)A(3) 不交换,A(3)A(4) 交换,A(4)A(5) 交换,用代码可表示为： For j=1 to 4 If

5、 a(j)a(j+1) then 交换a(j)和a(j+1)的值,冒泡排序过程数字化： 用冒泡法对5个数据排序（按从小到大的顺序）,第 二 轮 比 较,原始数据,A(1),A(2),A(3),A(4),A(5),162,155,182,164,157,第一次,164,157,182,164,157,155,182,164,157,162,155,182,164,157,182,162,155,157,164,162,155,182,162,155,157,182,162,155,164,157,182,162,155,164,157,182,162,155,164,157,182,162,15

6、5,164,157,182,162,155,164,157,182,162,155,182,162,155,164,157,第二次,182,162,164,155,157,第三次,A(1)A(2) 不交换,A(2)A(3) 交换,A(3)A(4) 交换,用代码可表示为： For j=1 to 3 If a(j)a(j+1) then 交换a(j)和a(j+1)的值,冒泡排序过程数字化： 用冒泡法对5个数据排序（按从小到大的顺序）,第 三 轮 比 较,原始数据,A(1),A(2),A(3),A(4),A(5),162,155,182,164,157,第一次,164,157,182,164,157

7、,155,182,164,157,162,155,182,164,157,182,164,162,157,155,162,155,182,162,155,157,182,162,155,164,157,182,162,155,164,157,182,162,155,164,157,182,162,155,164,157,182,162,155,164,157,182,162,155,182,164,162,157,155,第二次,A(1)A(2) 交换,A(2)A(3) 不交换,用代码可表示为： For j=1 to 2 If a(j)a(j+1) then 交换a(j)和a(j+1)的值,冒

8、泡排序过程数字化： 用冒泡法对5个数据排序（按从小到大的顺序）,第 四 轮 比 较,原始数据,A(1),A(2),A(3),A(4),A(5),162,155,182,164,157,第一次,164,157,182,164,157,155,182,164,157,162,155,182,164,157,162,155,182,162,155,157,182,162,155,164,157,182,162,155,164,157,182,162,155,164,157,182,162,155,164,157,182,162,155,164,157,182,162,155,182,164,162,

9、157,155,A(1)A(2) 不交换,用代码可表示为： For j=1 to 1 If a(j)a(j+1) then 交换a(j)和a(j+1)的值,如果我们用一个变量i（变量i的值分别为1，2，3,4）来表示第一轮、第二轮、第三轮、第四轮，那我们能不能将上述代码合并成一段通用的代码呢？教师展示下图：,For j=1 to 5-i If a(j)a(j+1) then 交换a(j)和a(j+1)的值 Next j,代码如下：,其中，I的值为1，2，3，4分别表示第一轮，第二轮，第三轮，第四轮。那我们怎样把两者结合起来呢？在轮次发生变化时，比较次数也随之发生变化。,代码如下：,For i=

10、1 to 4 For j=1 to 5-i If a(j)a(j+1) then T=a(j) A(j)=a(j+1) A(j+1)=T End if Next j Next i,（1）将N个元素放入数组A中，并打印输出,（2）将N个元素利用冒泡法进行排序,（3）将排好序的数据打印输出,若数组下标是从1开始，则上述程序更改为：,前面所讲的程序中，数组下标是从1开始的，但默认情况下，数组从0开始，如果数组下标从0 开始，程序将如何更改？,思考？,如果，设数组A中有N个数据，而且数组A的下标从0开始，则上述程序可综合为：,（1）将N个元素放入数组A中，并打印输出,（2）将N个元素利用冒泡法进行排序,（3）将排好序的数据打印输出,小结：,冒泡排序的基本原理： 每两个相邻的数据进行比较，满足某一种条件（