资源简介

(共17张PPT)
课时33 桶排序
一、桶排序算法的基本思想
桶排序的基本原理是将数组中的元素分配到有限数量的桶中，再对每个桶中的元素进行排序，每个桶中元素的排序可以使用其他任意排序算法。最后将每个桶中的数据按照顺序依次取出，即得到排序后的结果。
如图所示，桶排序首先要根据原始数组的数值范围，将数组划分为 k 个相同大小的子区间，每个区间称为一个桶。
二、桶排序算法的过程
def bucket_sort(arr):
#找到数组中的最大值和最小值
max_val=max(arr)
min_val=min(arr)
bucket_size=len(arr) #桶的大小
#计算桶的数量
bucket_range=max_val-min_val+1
bucket_num=bucket_range//bucket_size+1
#初始化桶
buckets=[[] for i in range(bucket_num)]
#将数组元素分配到桶中
for num in arr:
index=(num-min_val)//bucket_size
buckets[index].append(num)
#对每个桶中的元素进行排序
三、桶排序的 Python 实现
for bucket in buckets:
bucket.sort()
#合并桶中的元素
sorted_arr=[]
for bucket in buckets:
sorted_arr+=bucket
return sorted_arr
典例 1 有如下 Python 程序段：
s=input("请输入字符串：")
m=n=d=0
for i in s:
if "0"<=i<="9":
d+=1
elif "a"<=i<="z":
m+=1
elif "A"<=i<="Z":
n+=1
print(m,n,d)
执行该程序段后，输入的内容为“2025,Best Luck!”，输出的结果是 （　　）
A.4 6 2 B.6 4 4 C.2 6 4 D.6 2 4
D
√
题型导向一　桶的算法思想应用
胜券点拨1
明考向 本题主要考查简单Python程序和桶思想
审关键 输出变量的顺序
考场思 维快闪 该算法采用了桶的思想，变量d统计数字字符的数量，变量m统计小写字母的数量，变量n统计大写字母的数量，因此最终m的值为6，n的值为2，d的值为4
典例 2 有如下 Python 程序段：
nums=[64,25,12,22,11]
bs=5
bn=(max(nums)-min(nums))//bs+1
t=[[] for i in range(bn)]
for num in nums:
i=(num-min(nums))//bs
t[i].append(num)
for i in range(len(t)):
t[i]=sorted(t[i])
s=[]
for item in t:
for j in item:
s.append(j)
print(s)
执行该程序段后，输出的结果是 （　　）
A.[11,25,12,22,64] B.[12,11,25,22,64] C.[11,12,22,25,64] D.[64,25,22,12,11]
C
√
题型导向二　桶排序的应用
胜券点拨2
明考向 本题考查桶排序算法的程序实现
审关键 桶排序算法实现过程中的语句作用
考场思 维快闪 该程序段实现对数组nums进行桶排序，变量bs为桶的大小，变量bn为桶的数量，第1个for语句将数组nums中的元素分配到对应的桶中，第2个for语句对每个桶中的元素进行升序排序，最后1个for语句将各个桶中的元素合并到数组s中，即s存储数组nums升序排序的结果
典例 3 编写 Python 程序，实现随机产生 100 个 0 到 99 之间的整数，然后将这 100 个数按照升序进行排序。实现上述功能的 Python 程序如下，请在画线处填入合适的代码。
import random
n=100
b=[[] for i in range(10)]
c=[0]*10
r=[]
a=[random.randint(0,99) for i in range(n)]
print("原始数据：",a)
for i in range(n):
t=a[i]//10
　　　①　　　1
for i in range(len(b)):
for j in range(len(b[i])):
k=b[i][j]%10
　　　②　　　1
for n in range(len(c)):
for m in range(c[n]):
r.append(i*10+n)
c=[0]*10
print("排序结果：",r)
b[t].append(a[i])
c[k]=c[k]+1
胜券点拨3
明考向 本题考查桶排序算法思想
审关键 桶的分配
考场思 维快闪 该程序段首先随机生成100个0到99之间的整数存储在数组a中，假设生成的数据是均匀分布的，因此可以分为10个大桶（数组b），编号为0～9，根据a[i]//10的结果将100个数分配到对应的大桶中（b[t].append(a[i])），这样各个大桶的相对大小就是升序排列的，但是大桶内的元素还是无序的，此时需要对各个大桶内的元素分别进行排序。该程序段采用桶排序对大桶内元素进行排序，将大桶又分为了10个小桶（数组c），根据大桶内元素除10取余的结果分配到对应的小桶中（c[k]=c[k]+1），例如：当i=1时，c[1]的值即数据11出现的次数；当i=2时，c[3]的值即数据23出现的次数。然后按照小桶的顺序和小桶内元素的数量添加到数组r中，就实现了大桶中元素的升序排序，每个大桶内的元素都完成排序后，100个整数即完成排序
1.有如下Python程序段：
a=[7,5,6,7,4,5]
b=[0]*10
for i in range(len(a)):
b[a[i]]+=1
pa=0
for i in range(9,-1,-1):
for j in range(b[i]):
a[pa]=i;pa+=1
print(a)
执行该程序段后，数组a的值是 （　　）
A.[7,7,6,5,5,4] B.[7,6,5,4]
C.[4,5,5,6,7,7] D.[4,5,6,7]
该程序段实现的是桶排序算法。数组a中的值在b中作为下标，每出现一次，将b中下标处元素的值加1，b[i]为数字i在数组a中出现的次数，从后往前遍历数组b，将值不为0的下标值根据出现次数依次再存入数组a中，得到元素值从大到小的非升序排序数组a。
一、桶的算法思想应用
A
√
2.有如下Python程序段：
b=[0]*10
for num in a:
b[num]+=1
k=0
for i in range(10):
a[k:k+b[i]]=[i]*b[i]
k+=b[i]
print(a)
若排序前数组a的值为[3,1,2,5,8,4,0,2,5]，则排序后数组a的值是 （　　）
A.[3,1,2,5,8,4,0,2,5] B.[0,1,2,3,4,5,8]
C.[0,1,2,2,3,4,5,5,8] D.[8,5,5,4,3,2,2,1,0]
该程序段实现的是桶排序算法。数组a中的值在数组b中作为下标，每出现一次，将b中下标处元素的值加1。b[i]为数字i在数组a中出现的次数。在数组b中遍历，将数值×数量依次存入到数组a中，最终得到数组a的元素值为从小到大的非降序排序。
C
√
二、桶排序的应用
3.有如下Python程序段：
li=[3,12,6,9,1,4,15]
n=max(li)
a_li=[0]*(n+1)
b_li=[]
for i in li:
a_li[i]+=1
for i in range(n+1):
if a_li[i]!=0:
for j in range(a_li[i]):
b_li.append(i)
执行该程序段后，sum(a_li)的值是 （　　）
A.15 B.7 C.3 D.0
B
√
该程序段实现的是桶排序算法，列表a_li的长度为列表li中的最大值n加1，即列表a_li中的下标值为0~n，可以看作n+1个桶，列表下标就是桶的编号，然后遍历列表li中的元素，将遍历到的数字li[i]存储到编号为li[i]的桶中，例如li中第一个数字是3，则列表a_li中下标为3处的元素值加1，表示存入了一个3。所以程序结束后，sum(a_li)的值即是所有“桶”中存储的元素总数，即li的长度7。
4.[2024.1浙江选考]某项活动有n个单位（编号1到n）参加，需将员工分成若干个小组，每个小组的人数上限为m，小组编号按新建次序从1开始编号。分组时，首先按单位编号次序依次在各单位内部分组，每m人分配到一个新建小组中，不足m人的剩余员工暂不分配；然后按剩余员工人数由大到小的顺序，依次为各单位剩余员工分配小组。
若某单位剩余员工人数为k，则分配方法为：在已建的小组中查找空位数（该小组还可容纳的人数）大于或等于k的小组，如果找到的小组有多个，则选择空位数最少的小组，将此k人分配到该小组中；如果没有找到，则新建一个小组，将此k人分配到该小组中。
设n为5，m为20，各单位员工人数及单位内部的分组过程如图a所示，各单位剩余员工的分组过程如图b所示。
　　编写程序：给定各单位编号及员工人数，根据上述方法进行分组处理，按单位编号次序输出各单位所分配的分组编号。请回答下列问题：
（1）由题意可知，若仅将图a中1号单位的员工人数修改为25，然后对图中5个单位重新分组，则1号单位所分配的分组编号为　　　　　　　。
1,8
调用该函数，若lst为[[1,0],[2,0],[3,18],[4,0],[5,19],[6,17]]，请回答①和②两个问题。
①虚线框中的程序段第1次执行后，关于lst中的剩余员工人数，下列说法正确的是　　　　　　　（单选，填字母）。
A.lst[0][1]数值最小　　
B.lst[0][1]数值最大
C.lst[5][1]数值最小　　
D.lst[5][1]数值最大
②虚线框中的程序段执行的次数为
　　 　。
（2）定义如下bubble_sort(lst)函数，参数lst的每个元素由单位编号和剩余员工人数2个数据项组成。函数的功能是根据每个单位的剩余员工人数，对lst进行降序排序。
def bubble_sort(lst):
n=len(lst)
for i in range(0,n-1):
for j in range(n-1,i,-1):
if lst[j-1][1]tmp=lst[j]
lst[j]=lst[j-1]
lst[j-1]=tmp
if lst[i][1]==0:
break
return
4
B
√
（3）实现分组功能的部分Python程序如下，程序中用到的列表函数与方法如图c所示，请在程序中画线处填入合适的代码。
图c
函数与方法 功能
w.append(x) 在列表w末尾添加元素x
x=w.pop() 将列表w末尾元素赋值给x，并将其从w中删除
#对剩余员工分组
while i　　　②　　　1
while jj+=1
if jv=b[j].pop()
else:
gnum+=1
v=gnum
a[data[i][0]].append(v)
　　　③　　　1
i+=1
#输出各单位的分组编号，代码略
'''读取小组人数上限存入m；读取1至n号单位的数据，依次存入列表data的data[0]至data[n-1]中。data[i]包含2个数据项，data[i][0]、data[i][1]分别存放单位编号及员工人数，代码略'''
group(data,m)
def group(data,m):
n=len(data)
a=[]
for i in range(n+1):
'''a[i]初始化为空列表，存放编号为i的单位所分配的分组编号'''
a.append([])　
gnum=0
for i in range(n):　#各单位内部分组
while data[i][1]>=m:
gnum+=1
k=data[i][0]
a[k].append(gnum)
　　　①　　　1
'''根据每个单位的剩余员工人数，对data进行降序排序'''
bubble_sort(data)　
b=[]
for i in range(m):
b.append([])
i=0　
data[i][1]-=m　或　data[i][1]=data[i][1]-m
j=data[i][1]
b[j-data[i][1]].append(v)
（1）分组情况如图所示。
（2）①考查冒泡排序，根据代码“if lst[j-1][1]

展开更多......

收起↑