信息学奥赛刷题笔记用C STL sort函数实现整数奇偶排序的高效解法第一次参加信息学奥赛时我遇到了一道看似简单却暗藏玄机的排序题——整数奇偶排序。当时我花了整整一个小时调试自定义比较函数才最终通过所有测试用例。这道题之所以成为经典正是因为它完美考察了选手对排序算法本质的理解尤其是如何利用C STL中的sort函数结合自定义比较规则解决实际问题。本文将分享我在多次竞赛中总结出的高效解法重点解析cmp函数的编写技巧与常见陷阱。1. 理解题目本质与排序规则整数奇偶排序的要求看似直白将给定的一组整数按照奇数在前偶数在后奇数部分降序偶数部分升序的顺序排列。但深入分析后你会发现这实际上定义了三种不同的比较规则奇偶优先级任何奇数都应排在偶数前面奇数内部排序当两个数都是奇数时较大的数排在前面降序偶数内部排序当两个数都是偶数时较小的数排在前面升序这种多层次的排序规则正是考察选手对复合比较条件的理解和实现能力。在实际竞赛中约30%的选手会在这个环节犯错要么忽略了优先级顺序要么混淆了升降序规则。2. STL sort函数与自定义比较2.1 sort函数的基本用法C STL中的sort函数是算法竞赛中最常用的排序工具其基本用法如下#include algorithm #include vector vectorint nums {3, 1, 4, 1, 5, 9}; sort(nums.begin(), nums.end()); // 默认升序排序sort函数的时间复杂度为O(N logN)在绝大多数情况下都能满足竞赛需求。但它的真正强大之处在于支持自定义比较函数这正是解决本题的关键。2.2 自定义比较函数的实现要点对于整数奇偶排序问题我们需要实现一个符合题目要求的比较函数。以下是几种常见的实现方式及其优劣对比方法一条件分支实现bool cmp(int a, int b) { if(a%2 1 b%2 1) // 都是奇数 return a b; // 奇数降序 else if(a%2 0 b%2 0) // 都是偶数 return a b; // 偶数升序 else // 一奇一偶 return a%2 1; // 奇数在前 }这种实现清晰易读但需要注意条件判断的顺序很重要必须先处理同奇同偶的情况最后的else分支要确保奇数始终排在偶数前面方法二逻辑表达式合并bool cmp(int a, int b) { return (a%2 b%2 a b) || (a%2 0 b%2 0 a b) || (a%2 !b%2); }这种写法更简洁但可读性稍差适合对逻辑运算熟悉的选手。在实际调试时我建议先用第一种写法确保逻辑正确后再考虑优化。3. 常见错误与调试技巧在实现自定义比较函数时即使是经验丰富的选手也容易犯一些典型错误。以下是三个最常见的陷阱优先级顺序错误先判断奇偶性还是先判断大小错误示例if(a b) return a%2;这种写法会导致排序结果完全不符合要求边界条件忽略忘记处理负数的情况C中负数的取模运算结果可能为负需要特别注意改进方法使用(a%2 ! 0)代替(a%2 1)比较函数不符合严格弱序比较函数必须满足传递性等数学性质错误示例if(a b) return true;会破坏排序稳定性调试时可以采用以下策略先用小规模数据测试如[1,2,3,4,5]打印中间结果验证比较逻辑对于复杂情况可以单独测试比较函数4. 性能优化与替代方案虽然题目数据量很小通常N10但了解不同解法的性能特点对竞赛很有帮助。4.1 分区分别排序法另一种思路是将奇数和偶数分开存储分别排序后再合并vectorint odds, evens; for(int num : nums) { if(num % 2) odds.push_back(num); else evens.push_back(num); } sort(odds.begin(), odds.end(), greaterint()); // 奇数降序 sort(evens.begin(), evens.end()); // 偶数升序 odds.insert(odds.end(), evens.begin(), evens.end());这种方法虽然需要额外空间但在某些情况下更易理解和维护。下表对比了两种方法的特性特性自定义比较法分区排序法空间复杂度O(1)O(N)代码复杂度较高较低可扩展性较强较弱排序稳定性依赖实现稳定4.2 其他排序算法的适用性虽然STL sort在大多数情况下是最佳选择但了解其他排序算法也有其价值快速排序与STL sort类似适合大规模数据归并排序稳定排序适合需要稳定性的场景插入排序对小规模数据N20可能更快在信息学奥赛中掌握多种排序算法的实现和特性能帮助你在不同场景下选择最优解。5. 竞赛实战建议根据我的参赛经验在处理排序问题时以下几点特别重要充分理解题目要求明确排序的每一个规则和优先级测试边界条件包括空数组、全奇数、全偶数等情况代码模板准备提前准备好常用的比较函数模板时间管理简单排序题应在15分钟内完成对于本题我推荐的标准解题流程是仔细阅读题目确认排序规则设计比较函数的逻辑结构实现并测试基本功能检查边界条件和特殊输入提交前进行最终验证记住在竞赛中正确性永远比优化更重要。先确保你的解法能正确工作再考虑优化性能。