资源简介

(共16张PPT)
冒泡排序
现有一组无序的纸牌为：9、4、8、6、3，请将数据变得有序。
什么是冒泡排序

冒泡排序是在一列数据中把较小的数据逐次向上推移的一种排序技术。
冒泡排序算法把待排序的n个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻的两个元素中的数据，将较小的数据换到上面的一个元素中。重复这一过程，直到处理完最后两个元素中的数据，称为一遍加工。
当第一遍加工完成时，最小的数据已经上升到第一个元素的位置。然后对余下的n-１个元素重复上述处理过程，直至最后进行余下两个数据的比较和交换。
由于每一遍加工都是将本遍最小的元素像气泡一样上浮至本遍的顶端位置，故称为冒泡排序。
任务一：
看动画，感知原理
学生游戏:
演动画，理解思想
我校有4位学生参加学生会主席竞选，得票数依次为：36,27,32,18。若采用冒泡排序算法对其按照自下而上，从小到大进行排序，请写出详细过程。
动画理解习题解析
1.四个无序数据的排序方向为（ ）
（自下而上/自上而下）
2.排序完成时，数据的有序结果是（ ）
（从小到大/从大到小）
5 四个无序数据需要经过几趟才排好序？
3.第一趟结束时，排到最上边的数是（ ）
A:最大值 B:最小值
4.每次数据比较、交换的规则是（ ）
A. （这一个数>上一个数）
B. （这一个数<上一个数）
自下而上
由小到大
B
B
3趟
分组探究
请三组同学分别按照相应的排序规则，将无序数列36，27，32，18排列成相应要求的有序数列。
1. （已完成）自下而上方向，排成从小到 大的有序数列
2. （第一组）自下而上方向，排成从大到小的有序数列
3. （第二组）自上而下方向，排成从小到大的有序数列
4. （第三组）自上而下方向，排成从大到小的有序数列
任务1：写出详细比较过程
任务2：比较趟数？每趟比较次数？比较和交换的原则？
冒泡排序的四种方式比较
冒泡方式 比较趟数 每趟比较次数 比较、交换规则
自下而上 从小到大 (这一个) < (上一个)
自下而上 从小到大 (这一个) >(上一个)
自上而下 从小到大 (这一个) > (下一个)
自上而下 从大到小 (这一个) <(下一个)
3
2
1
3
3
3
3
3
2
1
3
2
1
3
2
1
趟数 数据的比较过程 比较次数
第1趟　 　 第4个数---上一个 3次　
　
第3个数---上一个 第2个数---上一个 第2趟　 第4个数---上一个 2次
　
第3个数---上一个 第3趟 第4个数---上一个 1次
以自下而上，由小到大为例：
规律总结
比较趟数 数据比较过程 每趟比较次数
第1趟 第n个数---上一个 n-1 次
第n-1个数---上一个 …… 第2个数---上一个 …… …… ……
第n-1趟 第n个数---上一个 1次
推想：当n个数据排序呢？
结论：当有n个无序数据排序，需要几趟排序？
一共比较几次呢？
n-1
(n*(n-1))/2
四个数据怎样冒泡？
原始序列
a(1) 36
a(2) 27
a(3) 32
a(4) 18
最终序列
a(1) 18
a(2) 27
a(3) 32
a(4) 36
For j=4 to 2 step -1
if a(j)Next j
For j=4 to 3 step -1
if a(j)Next j
For j=4 to 4 step -1
if a(j)Next j
第一遍冒泡
第二遍
第三遍
J从4到2
J从4到3
J从4到4
i=1
i=2
i=3
i=1…2…3
For j=4 to i+1 step -1
if d(j)Next j
for i = 1 To 3
Next i
For j = 4 To i + 1 Step -1
Next j
If a(j) < a(j - 1) Then
End If
t= a(j): a(j) = a(j - 1): a(j - 1) = t
问1：5个数比较怎么改？
交换a(j) 和a(j-1)的值
For i = 1 To n-1
Next i
For j = n To i + 1 Step -1
Next j
t = a(j): a(j) = a(j - 1): a(j - 1) = t
If a(j) < a(j - 1) Then
End If
问：N个数排序呢
1、排序方向：自下而上/自上而下
2、有序：从大到小/从小到大
3、相邻两个数组元素进行比较
4、不符合排序要求，则交换
5、排序趟数
6、比较次数
课堂小结

展开更多......

收起↑