蓝桥杯算法入门（Python） 课件 第4章排序和排列

4.1十大排序算法蓝桥杯算法入门十大排序算法21.选择排序2.冒泡排序3.插入排序4.希尔排序5.计数排序6.桶排序7.基数排序8.归并排序9.快速排序10.堆排序大纲中的排序算法3组别知识点、难度大学C组排序：冒泡排序[2]、选择排序[3]、插入排序[3]大学B组排序：归并排序、快速排序、桶排序、堆排序、基数排序[4-5]选择排序（Selectionsort）4找最小的数，放在第1个位置；找第2小的数，放在第2个位置；......；找第n大的数，放在第n个位置。一共执行n-1轮操作第i轮找到第i小的数，放到第i个位置计算量O(n2)5defselection_sort():globala,nforiinrange(n-1):m=i

#m:记录a[i]~a[n-1]的最小数所在位置

forjinrange(i+1,n):#找a[i]~a[n-1]的最小数

ifa[j]<a[m]:m=ja[i],a[m]=a[m],a[i]#交换n=int(input())a=list(map(int,input().split()))selection_sort()print(*a)#或者：foriinrange(n):print(a[i],end="")冒泡排序（Bubblesort）6第一轮冒泡：比较a[0]和a[1]，如果a[0]>a[1]，交换。前2个数中的大数放到了第2个位置。

比较a[1]和a[2]，如果a[1]>a[2]，交换。把前3个数中的最大数放到了第3个位置。共n-1轮冒泡每一轮冒泡：把这轮的最大值放到a[i-1]计算量O(n2)7defbubble_sort():globala,nforiinrange(n-1):swapped=Falseforjinrange(n-i-1):ifa[j]>a[j+1]:a[j],a[j+1]=a[j+1],a[j]swapped=Trueifnotswapped:break#优化：这一轮冒泡没有发生交换，说明已经有序，结束n=int(input())a=list(map(int,input().split()))bubble_sort()print(*a)#或者：foriinrange(n):print(a[i],end="")插入排序（Insertionsort）8在一个有序数列上，逐个新增数据，当新增一个数x时，把它插入到有序数列中的合适位置，使数列仍保持有序。以{3,7,4,5,6,1,8,2}为例。（1）从第一个数a[0]开始。（2）新增a[1]，把它插到有序数列{a[0]}中。（3）新增a[2]，把它插到有序数列{a[0],a[1]}中。插n次，每次可能调整O(n)个数计算量O(n2)9definsertion_sort():globala,nforiinrange(1,n):key=a[i]#记下a[i]，准备把它插到前面合适的地方

j=i-1whilej>=0anda[j]>key:#若key比a[j]小

a[j+1]=a[j]#把a[j]往后挪，给key腾位置

j-=1a[j+1]=key#把key插到这里n=int(input())a=list(map(int,input().split()))insertion_sort()print(*a)#或者：foriinrange(n):print(a[i],end="")希尔排序（Shellsort）10{8,7,6,5,4,3,2,1}，共8个数，从小到大排序（1）gap=8/2=4，对间距为4的数排序。共4组数的间距为4，这四组数分别是{8,4}、{7,3}、{6,2}、{5,1}。分别在这4组数内部做插入排序。经过这一轮操作，较大的数挪到了右边，更靠近它们排序后的终止位置。11definsertion_sort(gap):globala,nforiinrange(gap,n):key=a[i]j=i-1whilej>=gap-1anda[j-gap+1]>key:a[j+1]=a[j-gap+1]j-=gap#若要测试计算量，在这里统计：cnt+=1a[j+1]=keydefshell_sort():forgapinrange(n//2,0,-1):#希尔排序的精髓在这里

insertion_sort(gap)n=int(input())a=list(map(int,input().split()))shell_sort()print(*a)#或者：foriinrange(n):print(a[i],end="")12（2）gap=4/2=2，对间距为2的数排序。共有2组数的间距为2，分别是{4,2,8,6}、{3,1,7,5}。分别做插入排序，例如{4,2,8,6}做插入排序的结果是{2,4,6,8}。例：处理8时，它前面的2、4已经排好序且更小，8不用做什么操作。这就是上一轮gap=4的排序操作带来的好处。13（3）gap=2/2=1，对间距为1的数排序由于前2轮的操作，到这一轮有很多数不用操作，例：{4,6,8}这3个数。例：处理到{5}时，它前面已经得到{1,2,3,4,6}，那么{5}只需要插到{6}前面即可。希尔排序的计算复杂度约为O(n1.5)。当n=105时，计算量约3000万次，远小于O(n2)的100亿次。计数排序（Countingsort）14基于哈希思想的排序算法，它使用一个额外的数组（称为计数数组）来统计每个数出现的次数，然后基于次数，输出排序后的数组。以数列a[]={5,2,7,3,4,3}为例。（1）找到最大值7，建计数数组cnt[8]；（2）把数列中的每个数看成cnt[i]的下标i，对应的cnt[i]计数。例如{5}对应cnt[5]=1，{2}对应cnt[2]=1，2个{3}对应cnt[3]=2。（3）遍历cnt[]，若cnt[i]=k，输出k次i。输出结果就是排序结果。计数排序的应用场景狭窄只适合“小而紧凑”的数列：所有的数值都不太大，且均匀分布15defcounting_sort():globala,nmax_num=max(a)#找到最大值

cnt=[0]*(max_num+1)#建数组cnt[]foriinrange(n):cnt[a[i]]+=1#把a[i]放到对应的空间里

i=0forjinrange(max_num+1):#输出排序的结果

whilecnt[j]>0:a[i]=ji+=1cnt[j]-=1n=int(input())a=list(map(int,input().split()))counting_sort()print(*a)#或者：foriinrange(n):print(a[i],end="")桶排序（Bucketsort）16（1）有k个桶，把要排序的n个数尽量均匀分到每个桶中；（2）要求桶之间也是有序的，即第i个桶内所有的数小于第i+1个桶内所有的数；（3）在每个桶内部排序；（4）最后把所有的桶合起来，就是排序的结果。桶排序：分治思想，分成k个桶基数排序（Radixsort）17以排序{5,47,23,19,17,31}为例。第1步：先按个位的大小排序，得到{31,23,05,47,17,19}。第2步：再按十位的大小排序，得到{05,17,19,23,31,47}。在位数比较小的情况下，即所有的数字差不多大时，是很好的方法。桶(基数)0123456789第1步

31

23

05

47、17

19第2步0517、19233147

18defradix_sort():globala,nexp=1max_num=max(a)#找出最大值，目的是找到最大数有多少位

tmp=[0]*len(a)whilemax_num//exp>0:#从个位开始，一直到最高位

bucket=[0]*10foriinrange(n):bucket[(a[i]//exp)%10]+=1foriinrange(1,10):bucket[i]+=bucket[i-1]foriinrange(n-1,-1,-1):k=(a[i]//exp)%10tmp[bucket[k]-1]=a[i]bucket[k]-=1foriinrange(n):a[i]=tmp[i]exp*=10n=int(input())a=list(map(int,input().split()))radix_sort()print(*a)#或者：foriinrange(n):print(a[i],end="")归并排序（Mergesort）19（1）分解。把初始序列分成长度相同的左右两个子序列，然后把每个子序列再分成更小的两个子序列……，直到子序列只包含1个数。（2）求解子问题，对子序列排序。（3）合并。归并两个有序的子序列，分治的妙用共logn趟归并每趟归并有O(n)次比较计算量O(nlogn)20defMerge(L,mid,R):globala,bi=Lj=mid+1t=0#一个子序列中的数都处理完了，另一个还没有，把剩下的直接复制过来：

while(i<=midandj<=R):if(a[i]>a[j]):b[t]=a[j]j+=1else:b[t]=a[i]i+=1t+=1while(i<=mid):b[t]=a[i]i+=1t+=1while(j<=R):b[t]=a[j]j+=1t+=1foriinrange(t):a[L+i]=b[i]#把排好序的b[]复制回a[]defMergesort(L,R):ifL<R:mid=(L+R)//2#平分成两个子序列

Mergesort(L,mid)Mergesort(mid+1,R)Merge(L,mid,R)#合并n=int(input())a=list(map(int,input().split()))b=[0]*len(a)Mergesort(0,n-1)print(*a)#或者：foriinrange(n):print(a[i],end="")快速排序（Quicksort）21快速排序：影响最大的排序算法，“TheTop10Algorithms”，20世纪十大算法之一。思路：把序列分成左右两部分，使得左边所有的数都比右边的数小；递归这个过程，直到不能再分为止。如何把序列分成左右两部分？最简单的办法是设定两个空间X、Y和一个基准数t；检查序列中所有的元素，比t小的放在X中，比t大的放在Y中。分治的妙用计算量O(nlogn)22defqsort(L,R):i,j=L,Rkey=a[(L+R)//2]whilei<=j:whilea[i]<key:i+=1whilea[j]>key:j-=1ifi<=j:a[i],a[j]=a[j],a[i]i+=1j-=1ifj>L:qsort(L,j)ifi<R:qsort(i,R)n=int(input())a=list(map(int,input().split()))qsort(0,n-1)print(*a)#或者：foriinrange(n):print(a[i],end="")堆排序（Heapsort）23用二叉堆来排序。二叉堆：一棵二叉树，如果是一棵最小堆，那么树根是最小值。性质：把树根取出后，新的树根仍然是剩下的树上的最小值。把要排序的n个数放进二叉堆，然后依次取出树根，就从小到大排好了序。

计算量O(nlogn)24importqueuen=int(input())a=list(map(int,input().split()))pq=queue.PriorityQueue()foriinrange(n):pq.put(a[i])#将输入的数插入小根堆whilenotpq.empty():print(pq.get(),end='')#依次输出，就是从小到大罗勇军4.2排序函数蓝桥杯算法入门sort()和sorted()函数261、sort()sort()函数是Python中列表对象的方法，用于对列表进行原地排序（即直接修改原始列表），没有返回值。sort()函数的语法： list.sort(key=None,reverse=False)key和reverse都是可选参数：key：用于指定排序的比较键。它可以是一个函数，该函数接受列表中的每个元素作为输入，并返回一个用于比较的键。默认值为None，表示使用元素本身进行比较。reverse：用于指定排序的顺序，reverse=True降序，reverse=False升序（默认）。计算复杂度：sort()是O(nlogn)的272、sorted()sorted()用于对可迭代对象进行排序，并返回一个新的已排序的列表。sorted()函数的语法： sorted(iterable,key=None,reverse=False)Iterable：要排序的可迭代对象，如列表、元组或字符串。key和reverse：可选参数：key：用于指定排序的比较键。它可以是一个函数，该函数接受可迭代对象中的每个元素作为输入，并返回一个用于比较的键。默认值为None，表示使用元素本身进行比较。reverse：用于指定排序的顺序，reverse=True降序，reverse=False升序（默认）。

排序的应用28简单排序自定义排序结构体排序字符串排序简单排序例题：输油管道问题http:///problem.php?id=109929问题描述：某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路径(或南或北)与主管道相连。如果给定n口油井的位置，即它们的x坐标（东西向）和y坐标（南北向），应如何确定主管道的最优位置，即使各油井到主管道之间的输油管道长度总和最小的位置。输入：输入第一行为正整数n(1≤n≤10000)；接下来n行，每行两个整数x,y，表示第i个油井的位置(-10000≤x,y≤10000)。输出：输出一行整数表示管道长度总和的最小值。题解30已知n个油井的y坐标，排个序：

y0≤y1≤...≤yn-1设主管道的y坐标是m，那么就是求|y0-m|+|y1-m|+...+|yn-1-m|的最小值。m大于y0小于yn-1，猜测是平均值，或者中位数。容易证明是中位数，例：n=7，m是y3；n=8，m是y3或y4。n=int(input())y=[]foriinrange(n):x,yi=map(int,input().split())#忽略x坐标

y.append(yi)y.sort()#对n个y值排序m=y[n//2]#m是中位数ans=0foriinrange(n):ans+=abs(m-y[i])print(ans)自定义比较函数例题：数位排序/problems/2122/learning/31问题描述：小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。例如，2022排在409前面，因为2022的数位之和是6，小于409的数位之和13。又如，6排在2022前面，因为它们的数位之和相同，而6小于2022。给定正整数n，m，请问对1到n采用这种方法排序时，排在第m个的元素是多少？输入：输入第一行包含一个正整数n。第二行包含一个正整数m。30%的评测用例，1≤m≤n≤300。50%的评测用例，1≤m≤n≤1000。100%的评测用例，1≤m≤n≤106。输出：输出一行一个整数表示答案。题解32本题看似不好做，实际上可以利用的自定义比较函数，简单地实现。defdigit_sum(x):#计算x的数位和

ans=0whilex:ans+=x%10x//=10returnans'''或者用字符串处理数位和defdigit_sum(x):#计算x的数位和

returnsum(map(int,list(str(x))))'''n=int(input())m=int(input())a=list(range(1,n+1))#赋值a[0]~a[n-1]=1~na.sort(key=lambdai:digit_sum(i))#自定义比较，按i的数位和排序print(a[m-1])结构体排序例题：排队接水https:///problem/P122333问题描述：有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。输入：第一行为一个整数n。第二行n个整数，第i个整数Ti表示第i个人的等待时间Ti。输出：输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。题解34让n个人按接水时间从小到大排序，那么平均等待时间就是最小的。每个人定义一个类，变量包括接水时间t和人的编号id。classNode:def__init__(self,id,t):self.id=idself.t=tdef__lt__(self,other):#定义比较

returnself.t<other.tn=int(input())t=list(map(int,input().split()))#输入n个人的接水时间a=[]foriinrange(0,n):a.append(Node(i+1,t[i]))#每人：编号、接水时间a.sort()foriinrange(n):print(a[i].id,end="")#输出排队顺序print()time=0#总等待时间foriinrange(n):#累加等待时间

time+=a[i].t*(n-i-1)print("%.2f"%(time/n))

#算平均时间，保留两位小数字符串排序例题：宇宙总统https:///problem/P178135问题描述：地球历公元6036年，全宇宙准备竞选一个最贤能的人当总统，共有n

个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。输入：第一行为一个整数n，代表竞选总统的人数。接下来有n

行，分别为第一个候选人到第n

个候选人的票数。输出：共两行，第一行是一个整数m，为当上总统的人的号数。第二行是当上总统的人的选票。题解36把选票的票数当成字符串进行比较，但是需要写一个字符串比较函数。以“1234”和“990”为例，直接按字符串比较，“1234”<“990”，但是按数字比较，1234>990，两者结果不同。所以需要自己写比较函数，当两个字符串等长时，直接按字符串比较；当两个字符串不等长时，长数字大于短数字。classCandidate:#候选人

def__init__(self,v,id):self.v=v#vote,得票数

self.id=id#编号

def__lt__(self,other):iflen(self.v)==len(other.v):#两数字长度一样，直接按字典序比较

returnself.v<other.vreturnlen(self.v)<len(other.v)#两数字长度不一样，长数字大于短数字p=[]n=int(input())foriinrange(n):v=input()p.append(Candidate(v,i+1))p.sort()print(p[n-1].id)print(p[n-1].v)罗勇军4.3排列和组合蓝桥杯算法入门手写全排列38以从{1,2,3,4}中选3个的排列为例。写3个for循环，第一层for循环是4选1；第二层for循环去掉已经选的一个，剩下的3个选1；第三层是剩下的2个选1。s=[1,2,3,4]foriinrange(4):#4选1forjinrange(4):ifj!=i:

#去掉已经选的一个，剩下3选1forkinrange(4):ifk!=jandk!=i:#剩下2选1print("%d%d%d"%(s[i],s[j],s[k]),end="")手写组合39排列数需要分先后，组合数不分先后。把求组合的代码，去掉if，然后从小到大打印即可。以从{1,2,3,4}中选3个的组合为例。s=[1,2,3,4]foriinrange(4):#循环3次，选3个数

forjinrange(i+1,4):#让第2个数比第1个大

forkinrange(j+1,4):#让第3个数比第2个大

print("%d%d%d"%(s[i],s[j],s[k]),end="")二进制法输出组合40用二进制的概念进行对照，子集正好对应了二进制。a=[1,2,3,4,5,6]n=3#打印前n个元素a[0]~a[n-1]的所有子集foriinrange(1<<n):print('{',end='')forjinrange(n):#打印一个子集，即打印i的二进制数中所有的1ifi&(1<<j):#从i的最低位开始，逐个检查每一位，如果是1，打印

print(a[j],end='')print('}',end=';')子集Øa0a1a1,a0a2a2,a0a2,a1a2,a1,a0二进制数00000