【每日一题】排序

写在前面排序是算法竞赛中最基础也最核心的技能之一。它不仅是快速查找、去重、贪心等算法的前置步骤更是自定义比较策略、多关键字排序、排序后贪心等高级技巧的基石。本文基于蓝桥杯官方课程与真题从基础排序到竞赛实战带你彻底掌握排序今日题单7道蓝桥杯真题涵盖自定义排序、贪心排序、排序后差分、排序后前缀和、字典序排序、数位排序六大核心场景。一、排序基础Python排序的两种姿势1.1sort()/sorted()—— 基础排序# 原地排序修改原列表a[3,1,4,1,5]a.sort()# [1, 1, 3, 4, 5]a.sort(reverseTrue)# [5, 4, 3, 1, 1]# 返回新列表不修改原列表bsorted(a)# [1, 1, 3, 4, 5]1.2key函数 —— 自定义排序依据# 按绝对值排序a[-3,1,-4,2]a.sort(keyabs)# [1, 2, -3, -4]# 按元组的第一元素升序第二元素降序a[(1,3),(1,2),(2,1)]a.sort(keylambdax:(x[0],-x[1]))# [(1, 3), (1, 2), (2, 1)]1.3cmp_to_key—— 完全自定义比较Python3 取消了cmp参数但保留了functools.cmp_to_keyfromfunctoolsimportcmp_to_keydefcompare(a,b):# 返回负数a排在b前面# 返回正数a排在b后面# 返回0相等ifab:return-1elifab:return1else:return0a.sort(keycmp_to_key(compare))二、排序六大技巧从入门到高手技巧1多关键字排序 ⭐高频考点场景先按成绩降序成绩相同按年龄升序students[(85,18),(90,17),(85,16),(90,18)]# 成绩降序年龄升序students.sort(keylambdax:(-x[0],x[1]))# 结果[(90, 17), (90, 18), (85, 16), (85, 18)]原理元组排序是逐元素比较的利用这个特性实现多关键字排序。技巧2排序后贪心 ⭐核心思想核心洞察排序后问题的结构往往变得清晰贪心策略更容易设计。常见模式排序后维护最值从大到小遍历维护当前最大值/最小值排序后差分计算相邻差值选择最优切断点排序后双指针一头一尾向中间靠拢技巧3自定义比较器处理特殊规则场景数字的大小不是数值大小而是某种自定义规则如封闭图形个数、拼接后的字典序等fromfunctoolsimportcmp_to_key# 示例按数位和排序defcompare(a,b):sum_asum(int(d)fordinstr(a))sum_bsum(int(d)fordinstr(b))ifsum_a!sum_b:return-1ifsum_asum_belse1return-1ifabelse(1ifabelse0)技巧4排序后去重/离散化# 去重a[3,1,4,1,5,9,2,6]asorted(set(a))# [1, 2, 3, 4, 5, 6, 9]# 离散化将大值映射到小值b[100,50,200,50]sorted_uniquesorted(set(b))# [50, 100, 200]rank{v:ifori,vinenumerate(sorted_unique)}# {50:0, 100:1, 200:2}b[rank[v]forvinb]# [1, 0, 2, 0]技巧5部分排序/选择Top Kimportheapq# 找最小的k个元素O(n log k)a[3,1,4,1,5,9,2,6]k3smallestheapq.nsmallest(k,a)# [1, 1, 2]# 找最大的k个元素largestheapq.nlargest(k,a)# [9, 6, 5]技巧6稳定排序与不稳定排序排序算法稳定性Python实现冒泡排序✅ 稳定a.sort()Timsort选择排序❌ 不稳定—插入排序✅ 稳定—归并排序✅ 稳定sorted()快速排序❌ 不稳定—堆排序❌ 不稳定—Python的sort()和sorted()都是稳定排序基于Timsort相等元素的相对顺序保持不变。三、每日一题实战演练 题目1阿坤老师的独特瓷器 ⭐⭐⭐ 排序逆向维护最值题目链接蓝桥杯3994题目描述给定n个瓷器每个有直径d和高度h。一个瓷器是独特的当且仅当它的直径是所有瓷器中最大的或者它的高度比所有直径比它大的瓷器的高度都要高。求独特瓷器的数量。核心思路按直径降序排序直径大的排前面逆向遍历维护最大高度从直径最大的开始维护当前见过的最大高度判断当前高度 ≥ 最大高度 → 独特瓷器nint(input())dh[]for_inrange(n):d,hmap(int,input().split())dh.append((d,h))# 按直径降序直径相同按高度升序其实无所谓dhsorted(dh,keylambdax:(-x[0],x[1]))ans1# 直径最大的一定是独特瓷器max_hdh[0][1]# 当前最大高度foriinrange(1,n):# 如果当前高度 之前所有直径更大的的最大高度ifdh[i][1]max_h:ans1# 更新最大高度max_hmax(max_h,dh[i][1])print(ans)复杂度时间O(n log n)空间O(n)关键细节排序方向是降序用-x[0]ans初始为1因为直径最大的瓷器一定是独特的max_h更新在判断之后确保比较的是之前的最大值 题目2封闭图形个数 ⭐⭐⭐ 自定义比较器题目链接蓝桥杯19733题目描述每个数字的大小由封闭图形个数决定0,4,6,9有1个8有2个其他有0个。排序规则封闭图形个数少的在前个数相同则数值小的在前。核心思路cmp_to_key自定义比较器先比封闭图形个数个数相同比数值。fromfunctoolsimportcmp_to_key# 每个数字的封闭图形个数ls[1,0,0,0,1,0,1,0,2,1]# 索引: 0 1 2 3 4 5 6 7 8 9nint(input())alist(map(int,input().split()))defcompare(a,b):# 计算封闭图形个数numasum(ls[int(i)]foriinstr(a))numbsum(ls[int(i)]foriinstr(b))# 先比个数ifnuma!numb:return-1ifnumanumbelse1# 个数相同比数值return-1ifabelse(1ifabelse0)a.sort(keycmp_to_key(compare))print(*a)复杂度时间O(n log n × digit)digit为数字位数关键细节cmp_to_key是 Python3 的自定义比较标准写法比较函数返回-1/0/1不是True/Falsestr(a)拆分每一位再查表计算封闭图形个数 题目3摆玩具 ⭐⭐⭐⭐ 排序后差分贪心题目链接蓝桥杯5888题目描述n个玩具按高度升序摆放分成k段使所有段的极差之和最小。核心思路排序后计算相邻差值diff[i] h[i] - h[i-1]贪心选最大差值切断整体极差 sum(diff)切断一个差值就省下这个差值选最大的k-1个差值切断n,kmap(int,input().split())hlist(map(int,input().split()))h.sort()# 确保升序# 计算相邻差值diff[h[i]-h[i-1]foriinrange(1,n)]# 贪心去掉最大的 k-1 个差值diff.sort(reverseTrue)# 总极差 - 最大的k-1个差值 最小极差和# 等价于剩下的 n-k 个差值之和print(sum(diff[k-1:]))复杂度时间O(n log n)空间O(n)关键细节diff有n-1个元素k段需要k-1个切断点sum(diff[k-1:])是简洁写法去掉最大的k-1个剩下的求和k1时diff[0:] 全部kn时diff[n-1:] 空列表和为0 题目4小蓝的零花钱 ⭐⭐⭐⭐ 前缀和判平衡排序后贪心题目链接蓝桥杯3236题目描述序列中奇数和偶数数量相等可以在某些位置切割代价为两端元素差的绝对值要求每段奇偶数量相等。有B元预算求最多切割几次。核心思路前缀和判平衡偶数1奇数-1cnt0表示可切割收集所有可切割位置的代价排序后贪心优先选择代价小的n,bmap(int,input().split())alist(map(int,input().split()))cnt0# 前缀中(偶数个数 - 奇数个数)res[]# 可切割位置的代价foriinrange(n-1):ifa[i]%20:cnt1else:cnt-1# 前缀奇偶数量相等可以切割ifcnt0:res.append(abs(a[i]-a[i1]))# 贪心优先选代价小的res.sort()ans0forcostinres:ifbcost:# 严格大于等于不切割b-cost ans1else:breakprint(ans)复杂度时间O(n log n)空间O(n)关键细节cnt的更新偶数1奇数-1不是反过来range(n-1)保证i1不越界b cost不是b cost原题逻辑是严格大于整体奇偶相等保证前缀相等则后缀也相等 题目5二进制王国【算法赛】⭐⭐⭐⭐ 自定义排序字典序题目链接蓝桥杯17035题目描述给定n个二进制字符串将它们拼接起来求字典序最小的拼接结果。核心思路自定义比较器a应该在b前面当且仅当ab ba字符串拼接后字典序比较fromfunctoolsimportcmp_to_key nint(input())s[]for_inrange(n):s.append(input())defcompare(a,b):# ab 和 ba 比较字典序ifabba:return-1# a排在前面elifabba:return1# b排在前面else:return0s.sort(keycmp_to_key(compare))print(.join(s))复杂度时间O(n log n × L)L为字符串平均长度关键细节不是按字符串本身字典序排而是按拼接后的字典序排ab ba是经典贪心策略适用于拼接最小/最大类问题证明思路反证法如果存在相邻两个不满足ab ba交换后字典序更小 题目6第k个数 ⭐⭐⭐⭐⭐ 字典序排序计数题目链接蓝桥杯3336题目描述给定n, k求1~n按字典序排列后的第k个数。核心思路不生成所有数字直接按前缀计数n,kmap(int,input().split())curr1# 当前前缀k-1# 已经占了第1个数字1whilek0:# 计算以curr为前缀的数字个数在1~n范围内firstcurr# 当前前缀的最小值lastcurr# 当前前缀的最大值count0whilefirstn:# [first, last] 范围内的数字都是以curr为前缀的countmin(n1,last1)-first first*10# 下一层curr0, curr00, ...lastlast*109# 下一层curr9, curr99, ...# 如果k在count范围内说明答案在以curr为前缀的子树中ifkcount:k-count# 跳过整个子树curr1# 尝试下一个前缀else:curr*10# 进入子树k-1# 占了一个位置curr本身print(curr)复杂度时间O(log n × log n)空间O(1)关键细节字典序1, 10, 100, ..., 11, 110, ..., 2, 20, ...count计算以curr为前缀的数字个数用区间计数first * 10,last last * 10 9扩展到下一层多一位k - 1是因为进入子树时curr本身占了一个位置四、排序专题应用场景总结应用场景排序技巧时间复杂度代表题目多关键字排序元组keyO(n log n)独特瓷器自定义规则排序cmp_to_keyO(n log n × f)封闭图形个数排序后贪心排序 遍历维护最值O(n log n)独特瓷器、摆玩具排序后差分排序 相邻差值O(n log n)摆玩具排序后前缀和排序 前缀统计O(n log n)零花钱字典序排序cmp_to_key拼接比较O(n log n × L)二进制王国字典序计数前缀树计数O(log² n)第k个数部分选择heapq.nsmallestO(n log k)Top K问题五、结语排序的魅力在于将无序变为有序让问题结构清晰可解。当你熟练运用这些技巧后很多看似复杂的贪心、DP、二分问题都会迎刃而解。学习建议熟记sort()和sorted()的区别掌握key和reverse参数重点掌握cmp_to_key它是处理复杂排序规则的利器培养排序后…的思维习惯排序后差分、排序后双指针、排序后贪心关注字典序问题它是字符串排序和树形结构的核心多练习拼接排序类问题理解ab ba的贪心证明如果本文对你有帮助欢迎点赞 收藏 ⭐ 关注 你的支持是我持续更新的动力