写在前面今天的3道题全部来自蓝桥杯算法赛真题难度梯度递进核心考点包括分离排序思想、贪心拼接策略、归并排序求逆序对、多关键字排序。这些题目看似简单但暗藏精妙设计是检验排序思维深度的绝佳试金石。 今日刷题清单题号题目来源类型难度核心考点1奇偶排序蓝桥杯17022分离排序⭐⭐列表推导式、分离排序、稳定合并2二进制王国蓝桥杯17035贪心自定义排序⭐⭐⭐⭐拼接比较、贪心证明、字典序最小3星际争霸蓝桥杯5092归并排序逆序对⭐⭐⭐⭐⭐归并排序、逆序对计数、多关键字排序一、奇偶排序 ⭐⭐1.1 题目描述给定n个整数要求将所有奇数按升序排在前面所有偶数按升序排在后面。输入n和数组a输出排序后的数组奇数在前偶数在后各自升序1.2 关键思路分离分别排序合并暴力思路遍历数组奇数放前面偶数放后面然后各自排序。时间O(n log n)。更优思路利用 Python 列表推导式一行分离奇偶再分别排序合并。核心洞察奇数和偶数的相对顺序不需要交错可以完全分离分离后各自排序再拼接即可1.3 推演验证输入: n6, a[3, 1, 4, 1, 5, 9, 2, 6] 分离 奇数: [3, 1, 1, 5, 9] 偶数: [4, 2, 6] 各自排序 奇数: [1, 1, 3, 5, 9] 偶数: [2, 4, 6] 合并: [1, 1, 3, 5, 9, 2, 4, 6] 等等样例输出应该是 假设输入: [3, 1, 4, 1, 5, 9, 2, 6] 奇数排序: [1, 1, 3, 5, 9] 偶数排序: [2, 4, 6] 输出: 1 1 3 5 9 2 4 61.4 题解nint(input())alist(map(int,input().split()))# 分离奇数和偶数odd[xforxinaifx%21]# 奇数even[xforxinaifx%20]# 偶数# 各自排序后合并输出print(*(sorted(odd)sorted(even)))复杂度时间O(n log n)排序空间O(n)1.5 关键细节坑点说明x % 2 1判断奇数Python中负数取模结果可能为负但题目数据通常为正整数*解包输出print(*(list))等价于print(list[0], list[1], ...)去掉方括号列表推导式效率O(n)遍历比filter更 Pythonic稳定排序sorted()是稳定排序相等元素相对顺序不变二、二进制王国 ⭐⭐⭐⭐2.1 题目描述给定n个二进制字符串将它们拼接起来求字典序最小的拼接结果。输入n和n个二进制字符串输出字典序最小的拼接字符串2.2 关键思路自定义比较器贪心暴力思路枚举所有排列拼接后比较字典序。n!种排列不可接受。优化思路贪心策略——a应该在b前面当且仅当ab ba字符串拼接后字典序比较。为什么ab ba是对的证明思路交换论证假设最优排列中存在相邻两个字符串a, b满足ab ba交换它们得到..., b, a, ...比较两种排列... a b ...vs... b a ...由于ab ba交换后字典序更小与最优矛盾所以最优排列中任意相邻两个都满足ab ≤ ba传递性这种比较关系满足传递性可以严格证明所以可以用排序实现。2.3 推演验证输入: n3, s[10, 1, 11] 所有排列及拼接结果 [10,1,11] → 10111 [10,11,1] → 10111 [1,10,11] → 11011 [1,11,10] → 11110 [11,1,10] → 11110 [11,10,1] → 11101 字典序最小: 10111 用贪心策略验证 比较 10 和 1: 101 101, 110 110 101 110所以 10 应该在 1 前面 比较 10 和 11: 1011 1011, 1110 1110 1011 1110所以 10 在 11 前面 比较 1 和 11: 111 111, 111 111 相等相对顺序不变稳定排序 排序结果: [10, 1, 11] 或 [10, 11, 1] 拼接: 10111 ✓2.4 题解fromfunctoolsimportcmp_to_key nint(input())s[]for_inrange(n):s.append(input().strip())defcompare(a,b): 比较函数ab 和 ba 的字典序 返回 -1: a 排在 b 前面ab ba 返回 1: a 排在 b 后面ab ba 返回 0: 相等 ifabba:return-1elifabba:return1else:return0# 自定义排序s.sort(keycmp_to_key(compare))# 拼接输出print(.join(s))复杂度时间O(n log n × L)L为字符串平均长度2.5 关键细节坑点说明ab ba不是a b直接比较字符串本身是错误的必须用拼接后比较cmp_to_key用法Python3 标准写法将比较函数转为 key 函数稳定排序当ab ba时返回0保持原有相对顺序字符串拼接复杂度每次比较O(L)总复杂度O(n log n × L)输入读取input().strip()去除首尾空白避免换行符干扰三、星际争霸 ⭐⭐⭐⭐⭐3.1 题目描述星际争霸中每个士兵有一个战斗力字符串由0-9组成。定义一个字符串的混乱度为将其转换成列表后逆序对的个数。现在给定n个士兵的战斗力字符串按以下规则排序混乱度升序逆序对数小的在前混乱度相同字符串长度升序长度也相同字符串本身字典序升序输入n和n个字符串输出排序后的字符串列表3.2 关键思路归并排序求逆序对 多关键字排序第一步求逆序对个数逆序对定义数组中i j但a[i] a[j]的对数。归并排序求逆序对归并排序的分治过程中当arr[i] arr[j]时arr[i...m]都大于arr[j]贡献m-i1个逆序对时间O(n log n)第二步多关键字排序排序规则第一关键字逆序对数升序第二关键字字符串长度升序第三关键字字符串本身字典序升序Python 实现arr.sort(keylambda x: (x[0], len(x[1]), x[1]))3.3 推演验证输入: n3 s [21, 123, 321] 计算逆序对 21 → [2,1] → 逆序对: (2,1) → 1个 123 → [1,2,3] → 逆序对: 0个 321 → [3,2,1] → 逆序对: (3,2),(3,1),(2,1) → 3个 排序 (123, 0, 3) → 第一 (21, 1, 2) → 第二 (321, 3, 3) → 第三 输出: 123, 21, 3213.4 题解defmerge_sort(arr,l,r): 归并排序同时计算逆序对个数 arr: 待排序数组整数列表 l, r: 左右边界闭区间 返回: 逆序对个数 iflr:return0m(lr)//2leftmerge_sort(arr,l,m)# 左半部分逆序对rightmerge_sort(arr,m1,r)# 右半部分逆序对returnleftrightmerge(arr,l,m,r)# 跨区间逆序对defmerge(arr,l,m,r): 合并两个有序区间 [l,m] 和 [m1,r] 同时计算跨区间逆序对 temp[0]*(r-l1)# 临时数组il# 左半部分指针jm1# 右半部分指针idx0# temp数组指针res0# 逆序对计数# 双指针合并whileimandjr:ifarr[i]arr[j]:# 左边小直接放入temp[idx]arr[i]i1else:# 右边小说明 arr[i...m] 都大于 arr[j]# 贡献 m - i 1 个逆序对resm-i1temp[idx]arr[j]j1idx1# 处理剩余元素whileim:temp[idx]arr[i]i1idx1whilejr:temp[idx]arr[j]j1idx1# 复制回原数组arr[l:r1]tempreturnres# 主程序nint(input())arr[]for_inrange(n):sinput().strip()# 将字符串转为整数列表计算逆序对num_listlist(s)# 如 21 → [2, 1]inversion_countmerge_sort(num_list,0,len(num_list)-1)# 保存 (逆序对数, 原字符串)arr.append((inversion_count,s))# 多关键字排序# 1. 逆序对数升序# 2. 字符串长度升序# 3. 字符串字典序升序arr.sort(keylambdax:(x[0],len(x[1]),x[1]))# 输出结果forinfoinarr:print(info[1])复杂度计算逆序对O(L log L)L为字符串长度总时间O(n × L log L n log n)空间O(L)归并排序临时数组3.5 关键细节坑点说明归并排序中的arr[i] arr[j]必须是不是保证稳定性避免重复计数res m - i 1当arr[i] arr[j]时arr[i...m]都大于arr[j]共m-i1个字符串转列表list(s)得到字符列表merge_sort按字符 ASCII 比较多关键字排序keylambda x: (x[0], len(x[1]), x[1])元组逐元素比较临时数组大小temp [0] * (r - l 1)注意是闭区间长度r-l13.6 归并排序求逆序对原理数组: [3, 1, 4, 2] (索引0~3) 分治过程: [3,1,4,2] → [3,1] 和 [4,2] [3,1] → [3] 和 [1] 合并: 3 1res 1-01 13的逆序对 结果: [1,3], res1 [4,2] → [4] 和 [2] 合并: 4 2res 1-01 14的逆序对 结果: [2,4], res1 合并 [1,3] 和 [2,4]: i0(1), j2(2): 1 2, 放入1, i1 i1(3), j2(2): 3 2, res 2-11 23和2, 3后面的...等等 等等m1左半部分最后一个索引 i1(3), j2(2): 3 2, res m - i 1 1 - 1 1 1 放入2, j3 i1(3), j3(4): 3 4, 放入3, i2左半部分结束 放入4 总逆序对: 1 1 1 3 验证: (3,1), (3,2), (4,2) → 3个 ✓ 今日复盘总结题目核心技巧思维路径易错点国赛价值奇偶排序分离排序奇偶分离→各自排序→合并*解包输出、列表推导式基础技巧二进制王国贪心拼接排序相邻交换论证→abba→自定义排序比较器返回值、字符串拼接方向经典贪心星际争霸归并排序逆序对分治求逆序对→多关键字排序稳定性、m-i1计数、多关键字综合应用 今日核心收获分离排序思想当数据可以清晰分类时先分离再各自排序最后合并往往比复杂比较器更简洁。贪心拼接策略ab ba是解决拼接最值类问题的通用贪心策略记住交换论证的证明方法。归并排序求逆序对分治过程中统计跨区间逆序对时间O(n log n)是处理顺序对/逆序对问题的标准算法。多关键字排序Python 中用元组keylambda x: (key1, key2, key3)逐元素比较简洁高效。稳定排序的重要性当比较相等时稳定排序保持原有顺序这在多轮排序或复杂规则中至关重要。 排序算法复杂度对比算法平均时间最坏时间空间稳定性Python实现冒泡排序O(n²)O(n²)O(1)✅—选择排序O(n²)O(n²)O(1)❌—插入排序O(n²)O(n²)O(1)✅—归并排序O(n log n)O(n log n)O(n)✅sorted()/sort()快速排序O(n log n)O(n²)O(log n)❌—堆排序O(n log n)O(n log n)O(1)❌heapqTimsortO(n log n)O(n log n)O(n)✅Python内置Python 的sort()和sorted()使用Timsort归并排序插入排序的混合是稳定排序。记得点赞收藏算法路上不迷路有问题评论区见