Nhomakorabea.
3
任务规则
• 4人一个小组； • 每组4张数字卡片和一张标有位置的纸； • 将4张卡片打乱，随机摆放在纸上； • 每个小组用自己的方法进行排序； • 排序时的两种操作：
– 取数（什么是取数？） – 交换（什么是交换？）
• 总结你们小组的排序规则；
.
4
小组演示
请思考： 该组所使用的排序方法能不能成为一种算法？
• 排序是计算机解决问题常用的算法之一，排序算法方法多 样，本节课只介绍了其中一种——冒泡排序，书上还介绍 了另外一个算法选择排序，有兴趣的同学可以按照本节所 用的方法自己研究一下，看看冒泡排序和选择排序有什么 区别，看看哪一个排序更快？
.
25
感谢亲观看此幻灯片，此课件部分内容来源于网络， 如有侵权请及时联系我们删除，谢谢配合！
4
j
.
41 5
28 3
18
冒泡排序（一般情况）
1 2
3
i
j -1
4
j
.
41 5
28 3
19
一般情况变化过程：
41，5，28，3 41，5，3，28 41，3，5，28 3，41，5，28 3，41，5，28 3，5，41，28 3，5，28，41
在本次冒泡排序中： 交换次数：？ 取数次数：？
.
20
冒泡排序（一般情况）
1
2
i
3 j -1
4
j
.
41 5
28 3
14
冒泡排序（一般情况）
1
2
i
3 j -1
4
j
.
41 5
28 3
15
冒泡排序（一般情况）
1
2
i
j -1
3
j
4
.
41 5
28 3
16
冒泡排序（一般情况）
1
2
i
j -1
3
j
4
.
41 5
28 3
17
冒泡排序（一般情况）
1 2
3
i
j -1
1
i
2
3 j -1
4
j
.
41 5
28 3
9
冒泡排序（一般情况）
1
i
2
j -1
3
j
4
.
41 5
28 3
10
冒泡排序（一般情况）
1
i
2
j -1
3
j
4
.
41 5
28 3
11
冒泡排序（一般情况）
1
i j -1
2
j
3
4
.
41 5
28 3
12
冒泡排序（一般情况）
1
i j -1
2
j
3
4
.
41 5
28 3
13
.
5
冒泡排序
.
6
什么是冒泡排序？
• 把待排序的几个数据竖直堆放，从最下面的一个数据起， 自下而上比较相邻的两个位置的数据，将数值较小的数据 换到靠上位置（交换），然后重复这一过程，直到处理完 最后位置的两个数据。（P59）
.
7
冒泡排序（一般情况）
1
i
2
3 j -1
4
j
.
41 5
28 3
8
冒泡排序（一般情况）
• 按照冒泡排序算法再对5张数字卡片进行排序； • 记录卡片的初始状态及每一次调整后的状态； • 记录取数次数和交换次数；
.
24
小结
• 每天我们用计算机完成各种各样的任务，表面上看是计算 机在为人服务，实际上是人们将思维形式化为计算机可以 执行的步骤，再编写成程序让计算机执行，其中的步骤就 是算法。
最糟情况变化过程：
41 41 41 3 3 3 3 28 28 3 41 41 5 5 5 3 28 28 5 41 28 3 5 5 5 28 28 41
在最糟情况冒泡排序中：
交换次数：？
取数次数：？
.
21
.
22
提问：
• 如果要13张卡片进行冒泡排序，取数多少 次？交换多少次？
.
23
冒泡排序练习
• 大家都玩过扑克牌的游戏，无论玩什么样 扑克牌游戏，拿到牌以后总要做的一件事 情是什么？
.
1
什么是排序？
• 排序：
某些问题的处理过程依赖于数据的有序性，将杂乱无 章的数据变为有序的数据这一过程称为排序。
• 排序规则：
递增排序，递减排序； 非递增排序，非递减排序；
.
2
任务
• 有参加一百米决赛的4位运动员的成绩，你 的任务是对这4个成绩进行递增排序。