浙教版选修一 2.2 解析算法 课件（12张）

冒泡排序
冒泡排序:把较小的数据逐次向上推移的一种排序技术。
如何实现将较小数逐次从下向上推移呢？
从最后一个元素起，依次比较相邻的两个 元素中的数据，将较小的数据调换到上面。
1
2
3
4
5
第一轮冒泡排序过程
A(5)>a(4)保持不变
A(4)A(3)A(2)1
2
3
4
5
第二轮冒泡排序过程
A(5)>a(4)保持不变
A(4)A(3)1
2
3
4
5
第三轮冒泡排序过程
A(5)A(4)>a(3),不变
1
2
3
4
5
第三轮冒泡排序过程
A(5)规律：
1、冒泡排序的定义（以下为从小到大 升序）
将n个要排序的数看成一垂直列，从最下面的数开始，自下而上、两两比较相邻的两个数，把小的数向上换，经过n-1遍处理以达到排序目的的一种排序方法.
2、每次将最小的元素推至最前，称为一遍。
请同学表演怎样冒泡？
任务：请四位同学扮演4个数据（气泡）
规则：然后从后面开始两个两个比较你们的身高。如果后面的同学身高矮的话就和前面的同学调换位置。
初级目标：直到最矮的同学坐在最前面。
终极目标：从前到后，从矮到高有序排列。
需冒泡排列序列：17，3, 25, 14, 20, 9
执行过程：（每次将最小元素推至最前）
初始状态： 17 3 25 14 20 9
第一趟(轮)排序：3 17 9 25 14 20
第二趟(轮)排序：3 9 17 14 25 20
第三趟(轮)排序：3 9 14 17 20 25
第四趟(轮)排序：3 9 14 17 20 25
第五趟(轮)排序：3 9 14 17 20 25
巩固练习
6个学生的身高数据依次为172、168、185、178、164、175，采用冒泡排序算法对这些数据进行升序排序，第一遍加工（也称“第一趟冒泡”）后数据排列情形为：164、172、168、185、178、175.写出接下来每遍加工结束时数据的排列情形：
第2遍：
第3遍：
第4遍：
第5遍：
上述算法，总的冒泡趟数是___趟，而实际冒泡趟数（出现数据交换的趟数）又是___趟，相邻数据两两比较的总次数是___.
如果要对有6个元素的数组进行排序，那么
1、要进行________轮冒泡
…….
第五趟冒泡要经过 1 次比较
第一趟冒泡要经过 5 次比较
第二趟冒泡要经过 4 次比较
数据比较总次数：5+4+3+2+1=15
如果有N个数组的元素进行排序，则要进行_______ 趟冒泡
…….
第n-1趟冒泡要经过1次比较
第一趟冒泡要经过n-1次比较
第二趟冒泡要经过n-2次比较
比较总次数:(n-1)+(n-2)+(n-3)+………+2+1
即：n(n-1)/2
N-1