资源简介

(共28张PPT)
知识回顾
迭代算法：利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令，这组指令每执行一次时，都会将变量从原值递推出一个新值，即由旧值不断推出新值的过程。
f1 = 1
f2 = 1
i = 3
while i <= 12:
f = f1 + f2
f1 = f2
f2 = f
i += 1
print(f"第{i-1}月共有{f}对兔子“)
迭代算法处理问题：
确定迭代变量：由旧值递推出新值的变量；
建立迭代关系式：从变量的前值推出下个值的公式；
控制迭代条件：经过若干次重复执行后能够结束。
知识回顾
递归算法：在计算机科学中，指一种通过重复将问题分解为同类的子问题而解决问题的方法，它通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。
核心思想：把大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，规模较小的又转化为规模更小的问题求解，当问题小到一定程度时，可以直接得出它的解，从而回归求解问题原来的解。即“大事化小，小事化了”的思想。
实现条件：1、每一步解决问题的方法有一致的规律：递归公式
2、可以达到某个边界条件：递归出口
CHZX
5.3 数据排序
浙江省高中信息技术 选择性必修一 《数据与数据结构》
昌化中学 应彤鑫
冒泡排序
算法思想
程序实现
01
冒泡排序
Maopao paixu
算法思想
冒泡排序
Maopao paixu
算法思想
是一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。
三 要 素
趟数：n个数最多排 趟就完全有序
方向：从前往后、从后往前
升降：升序、降序
n-1
冒泡排序
Maopao paixu
算法实践
原始数据 170 176 165 183 162 比较次数 交换次数
第一趟 排序
第二趟 排序
第三趟 排序
第四趟 排序
170
165
176
162
183
4
2
165
170
162
176
183
3
2
165
162
170
176
183
2
1
162
165
170
176
183
1
1
4+3+2+1=10
2+2+1+1=6
总比较次数：
总交换次数：
冒泡排序
Maopao paixu
算法实践
原始 数据 170 176 165 183 162 比较次数 交换次数
第一趟
第二趟
第三趟
第四趟
原始 数据 170 176 165 183 162 比较次数 交换次数
第一趟
第二趟
第三趟
第四趟
原始 数据 170 176 165 183 162 比较次数 交换次数
第一趟
第二趟
第三趟
第四趟
原始 数据 170 176 165 183 162 比较次数 交换次数
第一趟
第二趟
第三趟
第四趟
①从前往后 升序
②从前往后 降序
③从后往前 升序
④从后往前 降序
170 165 176 162 183 4 2
165 170 162 176 183 3 2
165 162 170 176 183 2 1
162 165 170 176 183 1 1
176 170 183 165 162 4 2
176 183 170 165 162 3 1
183 176 170 165 162 2 1
183 176 170 165 162 1 0
162 170 176 165 183 4 4
162 165 170 176 183 3 2
162 165 170 176 183 2 0
162 165 170 176 183 1 0
183 170 176 165 162 4 3
183 176 170 165 162 3 1
183 176 170 165 162 2 0
183 176 170 165 162 1 0
练一练
有一组数为：6，2，9，8，7，4，经过一趟冒泡排序后的序列为：2，6，4，9，8，7，第二趟排序后的序列是（ ）
A.2,6,7,4,8,9 B.2,6,4,7,8,9
C.2,4,6,7,9,8 D.2,4,6,7,8,9
C
冒泡排序
Maopao paixu
程序实现——从前往后的升序
for j in range(______________):
If ____________________ :
for i in range(______________):
temp=a[j]
a[j]=a[j+1]
a[j+1]=temp
a[j]>a[j+1]
①如果符合条件，实现相邻两数交换
②每一趟升降的控制
当后者比前者小(升序)
③每一趟比较方向及次数的控制
④处理的趟数的控制
1 ,n
0,n-i
冒泡排序
Maopao paixu
程序变式——从前往后的降序？
for j in range(______________):
If ____________________ :
for i in range(______________):
temp=a[j]
a[j]=a[j+1]
a[j+1]=temp
a[j]>a[j+1]
①如果符合条件，实现相邻两数交换
②每一趟升降的控制
当后者比前者小(升序)
③每一趟比较方向及次数的控制
④处理的趟数的控制
1 ,n
0,n-i
a[j]练一练
有如下一段代码
a=[6,2,8,4,3,7]
length=len(a)
for i in range(1,length):
for j in range(0,length-i):
if a[j]>a[j+1]:
temp=a[j]
a[j]=a[j+1]
a[j+1]=temp
print(a)
Q1:这段代码实现的是冒泡排序算法，根据代码可知排序 （选填：从前往后或从后往前）的 （选填：升序/降序）。
Q2:代码运行结果为 。
其中第二趟排序结果为 。
从前往后
升序
[2,3,4,6,7,8]
[2,4,3,6,7,8]
冒泡排序
Maopao paixu
自定义函数的使用
对于需要重复调用的冒泡排序算法，我们可以创建自定义函数bubble_sort()来实现
def bubble_sort(a):
n=len(a)
for i in range( 1 ,n ):
for j in range( 0,n-i ):
if a[j]>a[j+1]:
temp=a[j]
a[j]=a[j+1]
a[j+1]=temp
使用方法：
a=[3,1,9,7,6]
bubble_sort(a)
print(a)
运行结果：
[1,3,6,7,9]
练一练
运行以下Python程序段后，输出的列表为(　　)
def bubble_sort(L)：
length＝len(L)
for i in range(1，3)：
for j in range(length，i，－1)：
if L[j]temp＝L[j]
L[j]＝L[j－1]
L[j－1]＝temp
a＝[6，8，2，4，3，7]
bubble_sort(a)
print(a)
A.[2，3，4，6，7，8] B.[8，7，6，4，3，2]
C.[2，3，4，6，8，7] D.[2，3，6，8，4，7]
D
冒泡排序
Maopao paixu
冒泡排序的程序优化
优化：
观察排序过程，可以发现第三趟冒泡排序后数组已经有序，后面两趟排序实际上没有做任何交换操作，因此可以设置一个标记变量flag来标记某趟排序过程中是否发生了交换。若无交换操作，表示已经完成排序，退出循环。
def bubble_sort(a):
n=len(a)
flag=False
for i in range( 1 ,n ):
for j in range( 0,n-i ):
if a[j]>a[j+1]:
temp=a[j]
a[j]=a[j+1]
a[j+1]=temp
flag=True
if not flag:
break
return a
练一练
有如下python程序段：
a=[2,1,9,8,6,3]
cnt=0
for i in range(len(a)-1,0,-1):
flag=False
for j in range(i):
if a[j]>a[j+1]:
a[j],a[j+1]=a[j+1],a[j]
flag=True
cnt+=1
if not flag:
break
则程序运行结束后，变量cnt的值为（ ）
A.3 B.4 C.5 D.6
B
思考
冒泡排序不足？
数据交换发生的太频繁，影响计算机处理速度
五个数据8,7,3,5,4，如何用尽可能少的交换次数，完成升序排序？
8
7
3
5
4
8
3
7
4
5
8
8
7
选择排序
算法思想
程序实现
02
选择排序
Xuanze paixu
概念：
选择排序
Xuanze paixu
算法思想
在排序数组的所有元素中找出最小（或最大）数据的元素，使它与第一个元素中的数据相互交换位置。然后在余下的元素中，找出最小（或最大）数据的元素与第二个元素中的数据相互交换位置。以此类推，直至排序完成。
核心要 素
趟数：n个数最多排 趟就完全有序
找最值（最大或最小）
和谁交换（第一个位置或最后一个位置）
n-1
选择排序
Xuanze paixu
43 56 23 15 50 78
原始数据
15
15 56 23 43 50 78
23
15 23 56 43 50 78
43
15 23 43 56 50 78
50
15 23 43 50 56 78
56
第1轮
第2轮
第3轮
第4轮
15 23 43 50 56 78
第5轮
问题1：
6个数据共需处理_____轮？
n个数据共需处理______轮？
5
n-1
问题2：
n个数据排序，最多交换次数为______次？
n-1
算法演算
问题3：
6个数一共比较了 次
如果有n个数据进行选择排序，共需要比较____________次？
n(n-1)/2
15
选择排序
Xuanze paixu
43 56 23 15 50 78
如何在数组中找到最小的数据？
43
23
15
15
最小的数据是15
算法演算
选择排序
Xuanze paixu
找到了最小数组元素后，如何交换？
如何确定最小元素在数组中的位置？
d[0] d[1] d[2] d[3] d[4] d[5]
43 56 23 15 50 78
确定元素的位置
记录数组元素的下标
K=0
K=2
K=3
K=3
K=3
最小的数据在d[k]
即d[3]
如何把最小的元素和第1个数组元素进行交换？
d[0],d[k]=d[k],d[0]
算法演算
选择排序
Xuanze paixu
算法演算
思考：如何在6个数据中找出最小的数据并与第1个数据进行交换？
（代码如何编写）
①先假设最小数组元素的下标为1
②利用循环语句逐个比较数组元素，并记录较小数据的数组下标
③将最小的数据与第1个数据进行交换
选择排序
Xuanze paixu
算法实现
k=0
for j in range( ):
If_____________ :
_______
t=d[0]
d[0]=d[k]
d[k]=t
If_____________ :
1,6
d[k]>d[j]
k=j
k!=0
第1轮
选择排序
Xuanze paixu
算法实现
推广到n个数据
k=0
for j in range( ):
If_____________ :
_______
t=d[0]
d[0]=d[k]
d[k]=t
If_____________ :
1,6
d[k]>d[j]
k=j
k!=0
for i in range( ):
0,n-1
i
i+1,n+1
i
t=d[i]
d[i]=d[k]
d[k]=t
选择排序
Xuanze paixu
算法实现
for i in range(0,n-2):
k=i
for j in range(i+1,n):
if a[k]>a[j]:
k=j
if k!=i:
a[i],a[k]=a[k],a[i]
①n个数据共需处理n-1轮
②利用k来记录最小元素的下标
③将余下的元素与最小元素进行比较，如果更小，则利用k记录该元素的数组下标
④每一轮比较结束判断最小元素的下标k是否发生改变，如果发生改变，则说明存在更小的元素，需进行数据交换；否则的话，说明最小元素就是假设的该轮最前方元素
练一练
有如下一段代码
a=[6,2,8,4,3,7]
n=len(a)
for i in range(0,n-2):
k=i
for j in range(i+1,n):
if a[k]>a[j]:
k=j
if k!=i:
a[i],a[k]=a[k],a[i]
print(a)
Q1:这段代码实现的是 （选填：冒泡排序或选择排序）算法，根据代码可知第一趟排序选取的是 （选填：最大值或最小值）放在 （选填：第一个或最后一个）位置。
Q2:代码运行结果为 。
其中第二趟排序结果为 。
选择排序
最小值
[2,3,4,6,7,8]
[2,3,8,4,6,7]
第一个

展开更多......

收起↑