数据结构基础知识05.-高考信息技术一轮二轮复习数据结构基础知识（浙教版2019）

数据结构基础知识（五）【知识要点】冒泡排序（要求：熟练掌握）工作原理：每次检查相邻两个元素，如果前后元素不满足升序(降序)就将相邻两个元素交换，当没有相邻元素需要交换时，排序就完成了。经i轮排序扫描，第i大(小)的数会被冒泡到数列的前面或后面2)稳定性：冒泡排序是一种稳定的排序算法3)时间复杂度：O(n2)defbubble_sort(a):#冒泡排序(升序)

foriinrange(1,len(a)):

#比较轮数=len1

forjinrange(len(a)i):#当前比较位置

ifa[j]>a[j+1]:

a[j],a[j+1]=a[j+1],a[j]

returnaa=[7,8,0,1,6,3,9,4,5,2]print(bubble_sort(a))我们发现最后两轮冒泡时已经有序，可以直接退出循环以提升算法效率defbubble_sort(a):#冒泡排序优化

foriinrange(1,len(a)):

#比较轮数=len1

flag=True#flag初始状态

forjinrange(len(a)i):

#当前比较位置

ifa[j]>a[j+1]:

a[j],a[j+1]=a[j+1],a[j]

flag=False#发生交换则标记flag

ifflag:break#若一轮都未发生交换则说明已经有序

returnaa=[7,8,0,1,6,3,9,4,5,2]print(bubble_sort(a))选择排序（要求：熟练掌握）工作原理：每次找出第i小(大)的元素，然后将这个元素和第i个位置元素交换2)稳定性：一般的认为选择排序是一种不稳定的算法3)时间复杂度：O(n2)defselection_sort(a):#选择排序(升序)

foriinrange(len(a)1):

ith=i

forjinrange(i+1,len(a)):

ifa[ith]>a[j]:

ith=j

#找到第i小的值位置

a[ith],a[i]=a[i],a[ith]

returnaa=[6,7,5,8,2,1,4,0,3,9]print(selection_sort(a))插入排序（要求：熟练掌握）工作原理：将待排元素分为“已排序”和“未排序”两个部分，每次从未排序部分中取出一个元素放到已排序中。稳定性：插入排序是一种稳定的算法时间复杂度：最优O(n)，最差O(n2)definsertion_sort(a):#插入排序(升序)

foriinrange(1,len(a)):

#小于i的为有序部分,i~len1为无序部分

val=a[i]

#无序部分取值

pos=i1

whilepos>=0anda[pos]>val:

#在有序部分寻找插入位置

a[pos+1]=a[pos]

#逐位后移

pos=1

a[pos+1]=val

#将值插入有序部分

returnaa=[6,0,9,5,8,3,4,7,1,2]print(insertion_sort(a))桶排序（要求：理解运行过程）工作原理：桶排序也并非常规的排序算法，它实际上是一种分治思想的实践。桶排序的过程可以分为4步：1.根据数据的特征将数据分为若干的桶，给每个桶规定可以存储的值的范围；2.将原数列的数据放入各个桶中；3.对每个桶都进行排序；4.按照桶的顺序将桶内数据重新链接。注意区分桶排序，归并排序，快速排序的区别。2)稳定性：桶排序的稳定性取决与其内层排序的排序算法3)时间复杂度：O(n2)#桶排序defbucket_sort(a):

bucket=[]

b=[]

bucketnum=(max(a)min(a))//len(a)+1#根据数据特征确定桶数量

foriinrange(bucketnum):

#建桶

bucket.append([])

forxina:#入桶

num=(xmin(a))//len(a)

bucket[num].append(x)

foriinrange(bucketnum):

bucket[i].sort()

#并非“脱了裤子放屁”，详见“注意”

b.extend(bucket[i])

#与b+=bucket[i]等价

print(bucket)#输出桶结构

returnba=[77,7,26,14,11,21,60,51,30,78]print(bucket_sort(a))#运行结果[[7,11,14],[21,26],[30],[],[51],[60],[],[77,78]]#桶结构[7,11,14,21,26,30,51,60,77,78]注意：桶排序更多适用与数据值域较大但分别较均匀的情况，其本质也只是用于分段，对于桶内数据一般不会再使用桶排序递归，而是采用更高效的排序算法。故示例再桶内排序时也直接使用了sort()方法加以区分和说明。归并排序（要求：理解运行过程）1)工作原理：归并排序是一种采用“分治思想”的排序方法。归并排序分为三个步骤：1.将数列分成左右两个部分；2.对左右两个部分进行并归排序；3.合并两个子序列。不难看出，并归中含有递归思想。2)稳定性：并归排序是一种稳定的排序算法3)时间复杂度：O(nlogn)4)空间复杂度：O(n)defmerge(a,left,mid,right):

#归并排序(升序)#两个有序数组合并(含头不含尾)

i=left;j=mid

b=[]

whilei<midandj<right:

ifa[i]<a[j]:

b.append(a[i]);i+=1

else:

b.append(a[j]);j+=1

whilei<mid:

b.append(a[i]);i+=1

whilej<right:

b.append(a[j]);j+=1

a[left:right]=b

#整理后复制回原数组

returnadefmerge_sort(a,left,right):

#归并(含头不含尾)

ifleft<right1:#子序列长度不为1

mid=(left+right)//2

a=merge_sort(a,left,mid)#归并左数列

a=merge_sort(a,mid,right)#归并右数列

a=merge(a,left,mid,right)#左右数列合并

returnaa=[8,0,2,5,9,7,3,4,6,1]print(merge_sort(a,0,len(a)))快速排序（要求：理解运行过程）1)工作原理：快速排序和归并排序类似，都采用了分治思想。快速排序也可以分为三个步骤：1.找一个值为基值，然后将小于基值的数放到基值左边，大于基值的数放到基值；2.对基值左右两部分再次进行快速排序；3.左右数列不需要合并已经有序。显然，快速排序也基于递归思想。2)稳定性：快速排序是一种不稳定的排序算法3)时间复杂度：最优O(nlogn)，最次O(n2)defpartition(a,low,hight):

#快速排序(升序)分段(左索引,右索引)

pivot_num=a[low]

#获取基值

whilelow<hight:

whilelow<hightanda[hight]>=pivot_num:

hight=1

a[low]=a[hight]

#比基值大的放在基值左侧

whilelow<hightanda[low]<=pivot_num:

low+=1

a[hight]=a[low]

#比基值小的放在基值右侧

pivot=low

a[pivot]=pivot_num

returna,pivot

#返回更新完的数列和基值位置defquick_sort(a,low,hight):

#快速排序(左索引,右索引)

iflow>=hight:

returna

a,pivot=partition(a,low,hight)

#将数组分为两个部分

a=quick_sort(a,low,pivot1)

#递归排序左半部分

a=quick_sort(a,pivot+1,hight)

#递归排序右半部分

returnaa=[5,4,8,3,6,2,9,1,7,0]print(quick_sort(a,0,len(a)1))希尔排序(缩小增量排序)（要求：在掌握插入排序基础上能够自主运用）1)工作原理：希尔排序是插入排序的一种改进版本，以其发明者希尔命名。希尔排序主要分三步处理排序问题：1.将待排序序列分为若干子序列；2.对子序列中相同位置的数进行插入排序；3.缩小每个子序列元素间的间距，重复过程直至间距缩小为1。2)稳定性：希尔排序是一种不稳定的排序算法。3)时间复杂度：希尔排序的时间复杂度和缩小间距的选取有之间关系。4)空间复杂度：O(n)defshell_sort(a):#希尔排序

delta=len(a)//2#间距

whiledelta>=1:

foriinrange(delta,len(a),1):

j=i

whilej>=deltaanda[j]<a[jdelta]:

#两个条件同时满足时,根据步长交换,使后面的较小数快速前移

a[j],a[jdelta]=a[jdelta],a[j]

j=delta#跳到前一组继续比较

delta//=2#调整间距

returnaa=[8,5,3,4,0,7,9,1,2,6]print(shell_sort(a))计数排序（要求：理解运行过程）1)工作原理：计数排序与常规排序不同，它使用一个额外的数组（或字典）去存储各个数据的个数，然后根据数组（或字典）中值的大小顺序重新复原数组。2)稳定性：计数排序是一种稳定的排序算法3)时间复杂度：计数排序的时间复杂度O(n)defcount_sort(a):#计数排序dic={};b=[]foriina:dic[i]=dic.get(i,0)+1#注意get()方法的使用forjinrange(min(a),max(a)+1):ifdic.get(j,0)>0:forkinrange(dic[j]):b.append(j)#print(dic)#用于输出字典结果，实际中不需要returnba=[9,8,3,5,1,4,9,6,4,4]print(count_sort(a))#运行结果{9:2,8:1,3:1,5:1,1:1,4:3,6:1}[1,3,4,4,4,5,6,8,9,9]注意：get(键,填充值)方法的使用，避免了字典查询为空的问题min()，max()方法的使用有点取巧，最值应该在第一次循环存字典时顺带统计。字典是一种无序结构，重新整合数组顺序由j循环控制基数排序（要求：理解运行过程）工作原理：基数排序是一种非比较排序算法，最早用与解决卡片排序问题。基数排序的过程：将待排序元素按位拆分，然后先排个位，再排十位，再排百位......对最高位排序结束后序列已经有序。2)稳定性：基数排序是一种稳定的排序算法3)时间复杂度：O(nklogn)4)空间复杂度：O(n)defradix_sort(a):#基数排序max_len=len(str(max(a)))foriinrange(1,max_len1,1):#位数循环b=[]bucket=[[]foriinrange(10)]#建桶，09共10个数forjina:try:radix=int(str(j)[i])#关键字，即个位，十位......except:radix=0bucket[radix].append(j)#print(bucket)forkinrange(10):#出桶iflen(bucket[k])>0:b.extend(bucket[k])#与b+=bucket[k]等价a=b#print(a)returnaa=[100,82,6,33,84,28,41,64,89,61]print(radix_sort(a))#运行结果：[100,82,6,33,84,28,41,64,89,61][[100],[41,61],[82],[33],[84,64],[],[6],[],[28],[89]]#第一次，个位入桶[100,41,61,82,33,84,64,6,28,89]#第一次结果[[100,6],[],[28],[33],[41],[],[61,64],[],[82,84,89],[]]#第二次十位入桶[100,6,28,33,41,61,64,82,84,89]#第二次结果[[6,28,33,41,61,64,82,84,89],[100],[],[],[],[],[],[],[],[]]#第三次百位入桶[6,28,33,41,61,64,82,84,89,100]#第三次结果堆排序（要求：了解即可）1)工作原理：堆排序使用了满二叉树结构（堆结构）尽心排序。首先将一维数列转为一个满二叉树（即父节点的索引i和子节点的索引j，满足j=i*2+1）,然后进行最大（小）堆调整。每次调整后根节点一定是最大（小）值，将根节点输出后堆剩余部分再进行最大（小）堆调整。2)稳定性：堆排序是一种不稳定的算法3)时间复杂度：O(nlogn)defmax_heapify(a,start,end):

#堆排序

最大堆调整

dad=start

#父节点

son=dad*2+1

#左子节点

whileson<=end:

#子节点索引不越界

ifson+1<=endanda[son]<a[son+1]:

#先比较左右子节点

son+=1

#若右节点更大，则交换节点更新为右节点

ifa[dad]<a[son]:

a[dad],a[son]=a[son],a[dad]

dad=son

son=dad*2+1

else:

breakreturnadefheap_sort(a):

#初始化调整，从最后一个父节点开始

foriinrange(len(a)//21,1,1):

a=max_heapify(a,i,len(a)1)

#最大堆的根节点一定是最大值，将最后一个节点替换根节点后再次排序

foriinrange(len(a)1,0,1):

a[0],a[i]=a[i],a[0]

a=max_heapify(a,0,i1)

returnaa=[5,1,9,6,8,7,2,0,3,4]print(heap_sort(a))【例题剖析】1.有如下Python程序段：b＝[56，78，11，31，24，52，66，49]count＝len(b)foriinrange(1,3)：forjinrange(0，count－i)：ifb[j]>b[j＋1]：b[j]，b[j＋1]＝b[j＋1]，b[j]经过该程序段“加工”后，列表b中的元素为()A.[11,24,31,52,49,56,66,78] B.[11,31,24,52,56,49,66,78]C.[56,11,31,24,52,66,49,78] D.[11,24,31,52,49,56,66,78]答案B解析本题主要考查的冒泡排序算法的程序实现。该程序段的功能是：采用冒泡排序算法进行升序排序2遍，数据比较是从前往后进行的，第1遍排序后列表b中的元素为[56,11,31,24,52,66,49,78]，第2遍排序后的数据序列为[11,31,24,52,56,49,66,78]，因此答案为B。2.有如下Python程序段：Ls＝["LiMing"，"WangPeng"，"ShengYi"，"ShaDan"，"XiaPo"，"ManGao"]n＝len(Ls)foriinrange(1，3)：forjinrange(0，n－i)：ifLs[j]<Ls[j＋1]：Ls[j]，Ls[j＋1]＝Ls[j＋1]，Ls[j]print("排序后的序列为："，Ls)经过该程序段“加工”后，列表Ls中的元素为()A.['LiMing','XiaPo','WangPeng','ShengYi','ShaDan','ManGao']B.['WangPeng','XiaPo','ShengYi','ShaDan','ManGao','LiMing']C.['WangPeng','ShengYi','XiaPo','ShaDan','ManGao','LiMing']D.['WangPeng','ShengYi','ShaDan','XiaPo','ManGao','LiMing']答案C解析本程序的功能是显示从左往右进行2趟降序排序后的数据序列，第1趟排序后的数据序列为"WangPeng"，"ShengYi"，"ShaDan"，"XiaPo"，"LiMing"，"ManGao"，第2趟排序后的数据序列为"WangPeng"，"ShengYi"，"XiaPo"，"ShaDan"，"LiMing"，"ManGao"。因此，答案为C。【习题巩固】1.有如下python程序段:a=[1]*6b=[96,88,84,91,99,80]foriinrange(6):forjinrange(i+1,6):ifb[j]>b[i]:a[i]+=1else:a[j]+=1该程序段运行后，列表a的值为（）A.[5,3,2,4,6,1]B.[2,4,5,3,1,6]C.[10,6,4,8,12,2]D.[4,8,10,6,2,12]2.有如下python程序段:lst=[74,32,66,46,38,28,85]k=1foriinrange(len(lst)1):iflst[i]*k<lst[i+1]*k:print(lst[i],end="")k=k执行完以上程序段后，输出的内容为()A.746638B.7432663828C.743266463828D.463.有如下python程序段:a=[int(i)forininput("请输入:").split()]#将以空格隔开的输入数以列表的形式存储m=len(a)whilem!=1;foriinrange(m1):ifa[i]>a[i+1]:a[i],a[i+1]=a[i+1],a[i]m=1print(a)执行程序后，输入的数字为3196，输出的结果为()A.[1,3,6,9]B.[9,6,3,1]C.[1,6,3,9]D.[9,3,6,1]4.有如下python程序段:fromrandomimportrandintlist=[0]*6foriinrange(6):list[i]=randint(10,99)foriinrange(2):forjinrange(5i):iflist[j]//10+list[j]%10>list[j+1]//10+list[j+1]%10:list[j],list[j+1]=list[j+1],list[j]print(list)该程序段运行后，列表list的值不可能为（）A.[54,17,26,40,73,85]B.[10,36,81,60,84,69]C.[33,81,15,46,19,69]D.[10,22,31,67,72,99]5.现有n个学生的7门学科成绩已存入一维数组cj中。某python程序代码段如下:deff(x):p=x*7;k=0forjinrange(7):ifcj[p+j]>cj[p+k]:k=jreturn(k)km="物化生政史地技"n=2;s=""foriinrange(n):s+=km[f(i)]print(s)cj数组元素的值依次为96,83,91,85,86,77,88,98,93,94,82,96,87,99,运行后,输出的结果为（）A.物技B.地政C.物生D.技物6.以下程序希望能实现随机序列的升序(从小到大)排列，则划线部分程序正确的是()importrandomarr=[]foriinrange(10):t=random.randint(1,100)arr.append(t)foriinrange(1,len(arr)):key=arr[i]j=ilwhile____①____:arr[j+1]=arr[j]j=l____②____print("排序后的数组:")foriinrang(len(arr)):print("%d"%arr[i])#依次输出ar中的每个元素A.①j>=0andkey<arr[j]②arr[j+1]=keyB.①j>=0andkey<arr[j]②arr[j]=keyC.①j>=0andkey>arr[j]②arr[j]=keyD.①j>=0andkey>arr[i]②arr[j+1]=key7.有如下Python程序段:La=["orange","banana","apple","grape","pear","mango"]count=len(La)foriinrange(0,2):forjinrange(count1,i,1):ifLa[j]<La[j1]:La[j],La[j1]=La[j1],La[j]经过该程序段“加工”后,列表La的元素为()A.["apple","orange","banana","grape","mango","pear"]B.["apple","banana","orange","grape","mango","pear"]C.["apple","banana","grape","orange","mango","pear"]D.["apple","banana","grape","mango","orange","pear"]8.小李基于冒泡排序算法编写了一个VB程序,功能如下:输入若干个待排序的数据,输出删除重复数据后的升序排序结果。程序运行示例如图所示。实现上述功能的VB程序如下,请回答下列问题:L2=input("Pleaseinputnumber:").split(",")print(L2)n=len(L2)foriinrange(0,n):L2[i]=eval(L2[i])bottom=n1i=0whilei<=bottom2:forjinrange(bottom,i,1):ifL2[j]<L2[i]:L2[j],L2[j1]=L2[j1],L2[j]elifL2[j]==L2[j1]:____①____bottom=bottom1i=i+1print("排序后的数据为:",____②____)(1)加框处的代码有误码，请改正。(2)请在程序划线处填入合适的代码。9.小明基于冒泡排序思想设计了一个改进的排序算法。该算法先用冒泡法将列表b中奇数位置的元素、偶数位置的元素分别进行排序，然后再进行后续处理。算法的Python程序段如下，请回答下列问题。b=[26,12,30,23,32,28,49,35,38]n=len(b)foriinrange(1,(n+1)//2):forjinrange(0,ni*2):if①________________:b[j],b[j+2]=b[j+2],b[j]foriinrange(1,n//2+1):j=2*i1ifb[j]<b[j1]:b[j],b[j1]=b[j1],b[j]foriinrange(1,n):t=b[i]j=i1whilet<b[j]:b[j+1]=b[j]j=1②____________________print("处理后的数据序列为：",b)(1)加框处的代码有误，请改正。(2)请在程序划线处填入合适的代码。10.小明为了研究冒泡排序过程中数据的“移动”情况，编写了一个Python程序，功能如下：第一行显示排序前的数据，输入初始位置(即下标值)后，输出指定初始位置的数据在排序过程中的位置变化情况，最后一行输出排序后的数据。程序运行示例如下图所示。请输入初始位置(索引值)：2排序前数据序列为：[43，23，65，12，26，33，58，19]位置变化情况：2→1→0排序后的数据序列为：[65，58，43，33，26，23，19，12]实现上述功能的Python程序如下，请回答下列问题。a＝[43，23，65，12，26，33，58，19]n＝len(a)pos＝int(input("请输入初始位置(索引值)："))①________________print("排序前数据序列为："，a)foriinrange(1，n)：forjinrange(0，n－i)：if②________________：a[j]，a[j＋1]＝a[j＋1]，a[j]ifpos＝＝j：pos＝j＋1s＝s＋"→"＋str(pos)elif③____________________：pos＝js＝s＋"→"＋str(pos)print("位置变化情况："＋s)print("排序后的数据序列为："，a)(1)请在程序划线处填入合适的代码。(2)程序运行样例如图所示，若输入的初始位置(索引值)为4，则输出的位置变化情况为____________________。11.某分段排序算法描述如下:1)将原始数据按非降序(a[1]<=a[2]<=a[3].....)分成两个有序段。2)将两个有序段进行合并，使得合并后的数据依旧有序，得到新的非降序段。如原始数据:1,3,4,5,7,9,2,6合并后结果:1,2,3,4,5,6,7,9编写Python程序，实现分段排序功能:读取“数据.txt”文件，如图所示，文件中每行有两段非降序数据，将每一行处理成一段非降序数据。请回答下列问题:(1)请在横线处填入合适的代码。(2)方框内为错误代码，请改正。(3)如果某一行的数据为“7,7,9,17,25,25”,则虚线框处代码执行后，k的值为 。#按行读取“数据.txt”文件，每次读一行文字存入字符串变量line中

f=open("数据.txt")

line=f.readline()

whileline:

sj=line.split(",")

#将字符串以”,”为间隔分割成多个字符串组成的列表

a=[0]*len(sj);b=[0]*len(sj)

foriinrange(len(sj)):

a[i]=①

k=0

forkinrange(len(a)1):

ifa[k]>a[k+1]:

break

else:

k=len(a)1

p=k

j=②

t=0;i=0

whilei<p+1orj<len(a):

ifj>=len(a)ori<panda[j]<a[i]:

b[t]=a[i];i=i+1

else:

b[t]=a[j];j=j+1

③

print(b)

line=f.readline()#读取下一行

f.close()12.学校为校庆选拔节目,每个班级先到A场地做“准备",然后到B场地“演出”。同一场地,同一时间只允许一个班级使用。每个班级使用A,B场地时间都有所不同。已知学校共n个班级,第i个班级使用A场地时长为a[i]分钟,使用B场地时长为b[i]分钟。为了更高效的组织这次选拔活动，某同学编写了如下Python程序计算此次活动的最小总时长和班级参加选拔的顺序。算法思路如下:1.统计m[i]表示第i个班级中在A和B两个场地中用时的较小值2.按m[i]值从小到大排序,然后按m[i]值的顺序,逐个班级安排参选顺序,策略如下:为了使得总时长最短,让A场地用时最少的最先开始;B场地用时最少的最后开始。对于每个班级,若m[i]与该班级在A场地使用时间相同,则将它排在剩余的可排位置的最前面,若m[i]与该班级B场地使用的时间相等,则将它安排在剩余可排位置的最后面。例如:n=5,班级序号分别是{1,2,3,4,5}1至5号班级使用A场地的时间依次为:{3