资源简介

(共19张PPT)
四、 冒泡排序算法及程序实现
第五章　数据结构与算法
知识过关
3. 冒泡排序的核心代码(以升序排序为例,对列表a进行排序,也可以使用函数形式)
(1)从后往前,小数往前冒。
　　n=len(a)
　　for i in range(1,n):
　　　　for j in range(n－1,i－1,－1):
　　　　　　if a[j－1]>a[j]:
　　　　　　　a[j],a[j－1]=a[j－1],a[j]
(2)从前往后,大数向后沉(变形)。
　　n=len(a)
　　for i in range(1,n):
　　　　for j in range(0,n－i):
　　　　　　if a[j]>a[j+1]:
　　　　　　　a[j],a[j+1]=a[j+1],a[j]
4. 冒泡排序的优化
冒泡排序中,若在某一遍排序的过程中未发生数据交换,则意味着数据已经有序,可以直接结束该冒泡排序。利用该特性,可以优化冒泡排序的程序代码(参考例4)。
典例精选
【例1】 (2023·浙江1月选考)列表s中包含了8个互不相等的元素,即s[0],s[1],s[2],…,s[7],有如下Python程序段:　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
n=8
for i in range(1,n－1):
　　for j in range(1,n－i－1):
　　　　if s[j]>s[j－1]:
　　　　　　s[j],s[j－1]=s[j－1],s[j]
该程序段实现的是(　　)
A. s[0]到s[5]的降序排列 B. s[1]到s[6]的降序排列
C. s[1]到s[7]的升序排列 D. s[2]到s[6]的升序排列
A
【解析】 本题考查冒泡排序算法思想。已知外循环变量i的取值范围是[1,6]。当第一轮比较(i为1)时,内循环变量j的取值范围是[1,5],由于参与比较的两元素下标分别是j和j－1,故列表中仅元素s[0]~s[5]从前向后进行比较。再观察分支语句条件s[j]> s[j － 1]可知,当后一个数大于前一个数时要发生交换,故最终排序结果是降序。A正确。
【例2】 有如下Python程序段:
k = 1
for i in range(0,len(a)－1):
　　if k*a[i] >k*a[i+1]:
　　　　a[i],a[i+1] = a[i+1],a[i]
　　k=－k
若列表a有7个元素,运行该程序后,a可能的值是(　　)
A. [7,8,5,9,6,9,7] B. [7,6,5,8,7,9,9]
C. [8,6,7,5,9,7,9] D. [7,8,6,5,7,9,9]
A
【解析】 本题考查冒泡排序知识。程序中,当i的值为偶数时k=1,i的值为奇数时k=－1,k的值依次为1、－1、1、－1……交替变换。由条件“k * a[i]> k * a[i + 1]”可知,当k=1时,程序运行后满足a[i]<=a[i + 1];当k=－1时,程序运行后满足a[i]>=a[i + 1]。程序运行后,对于列表a中的数据,满足索引值为偶数的数值必定小于等于其下一个相邻数值,索引值为奇数的数值必定大于等于其下一个相邻数值。A正确。
【例3】 随机生成n个范围是[10,59]的不重复随机整数,并用冒泡排序将其升序排列后输出。Python代码如下,运行界面如图所示。
import random
a=[0]*10
b=[False]*100
i=0
while i<=9:
　　　x=random.randint(10,59)
　　　while _______________:
　　　　　　x=random.randint(10,59)
　　　a[i]=x
　　　b[x]=True
　　　i=i+1
print(a)
def bub_sort(d):
　　　n=len(d)
　　　for i in range :　　　　　　　#①
　　　　　　for j in range :　　 #②
　　　　　　　　　if d[j]>d[j+1]:
　　　　　　　　　　　　　d[j],d[j+1]=d[j+1],d[j]
bub_sort(a)
print(a)
[10,16,15,50,30,26,13,23,47,54]
[10,13,15,16,23,26,30,47,50,54]
b[x]==True
(1,n)
(0,n－i)
请回答下列问题:
(1)请在画线处填入合适的代码。
(2)加框处①的代码能否修改为(0,n－1)或(n－1,0,－1) __________
(3)加框处②的代码能否修改为(n－i－1,－1,－1) __________
【解析】 (1)此处考查不重复随机数知识。列表b用于标记列表a中的数是否已经存在,False表示没有,True表示已经存在,因此若b[x]的值为True,则表示列表a中已经存在x,该值必须重新生成。(2)冒泡排序的外循环用于控制冒泡的遍数(轮数),n个数据,只需冒泡n－1轮即可实现有序排列,因此可以修改为(0,n－1)或(n－1,0,－1)。(3)冒泡排序具有方向性,而内循环主要用于控制冒泡的方向,而冒泡的方向不能简单地换方向,因此不能改为(n－i－1,－1,－1)。
能
不能
【例4】 n个数据的冒泡排序需要经过n－1遍加工,每一遍加工自下而上比较相邻两个数据,把较小者交换到上面。小刘发现,当某一遍加工过程中没有数据交换,说明数据已经有序,无须进一步加工。为此,小刘对算法进行优化,编写了一个Python程序,功能如下:运行程序时,在列表中显示排序前数据,然后在列表中显示这些数据按升序排序后的结果,最后显示排序过程的加工遍数。运行效果如图所示。
[30,18,49,67,69,36,88,21]
[18,21,30,36,49,67,69,88]
排序过程的加工遍数为:3
实现上述功能的代码如下。其中加框处的代码有错误,请改正。
import random
a=[0]*8
i=0
while i<=7:
　　　x=random.randint(10,99)
　　　a[i]=x
　　　i=i+1
print(a)
n=len(a)
i=1;flag=True
while i<=n－1 or flag=True :　　　　　　　　#改错①
　　　flag=False
　　　for j in range(n－1,i－1,－1):
　　　　　if a[j－1]>a[j]:
　　　　 　　a[j],a[j－1]=a[j－1],a[j]
　　　　 　　flag=True
　　　i+=1
print(a)
print("排序过程的加工遍数为:", str(i) )　　 #改错②
(1)加框处①的代码改为____________________________。
(2)加框处②的代码改为__________。
i<=n－1 and flag==True
str(i－1)
【解析】 本题考查冒泡排序的优化。冒泡排序可以进行优化,例如在某一轮冒泡中,没有数据交换,则意味着下一轮冒泡不需要继续进行,可以结束。①两个条件缺一不可,故应该是and。②外循环变量i从1开始,若本轮没有数据交换,则flag的值为False,此时i还要加1以后才能退出,因此共进行i－1轮冒泡排序,故答案是str(i－1)。
自我检测
1. 对5名学生按身高数据序列从低到高进行冒泡排序,第一遍加工后的结果为
“165,172,177,168,180”,则排序前这5名学生的身高数据序列不. 可. 能. 是(　　)
A. 172,177,165,168,180　　 B. 172,177,168,165,180
C. 172,165,177,168,180　　 D. 172,177,168,180,165
【解析】 本题要求以升序冒泡排序第一遍加工后的结果为依据,判定原始数据序列的可能情况。以升序冒泡排序C中数据,第一遍加工后的结果应该为“165,172,168,177,180”,C符合题意。
C
2. 采用冒泡排序算法对某数据序列进行排序,经过第一轮排序后的结果是“2,8,3,9,5,
6,7”,那么原数据序列不. 可. 能. 是(　　)
A. 8,3,9,5,2,7,6 B. 8,3,9,2,6,5,7
C. 8,2,9,3,5,7,6 D. 8,3,2,9,6,5,7
【解析】 本题考查对冒泡排序算法基本思想的理解。冒泡排序算法有从前(左)向后(右)和从后(右)向前(左)之分,还有升序和降序之分,且每一轮排序结束后必有一个数被调整到正确位置。由第一轮排序的结果是“2,8,3,9,5,6,7”可知,最小值2处于最前面的正确位置,即此冒泡排序实现从后(右)向前(左)的升序。由此推断,A、B、C的一轮排序结果均不符合题意。“8,3,2,9,6,5,7”的一轮排序结果为“2,8,3,5,9,6,7”,D符合题意。
D
3. 对10个数据进行冒泡排序,需要比较的次数是(　　)
A. 90 B. 110
C. 45 B. 55
【解析】 本题求规模为10的数据进行冒泡排序的比较次数。根据冒泡排序算法比较次数的计算方法可知,当n=10时,比较次数=10×(10－1)/2=45,C正确。
C

展开更多......

收起↑