C竞赛刷题实战STL sort函数在OpenJudge整数奇偶排序中的高阶应用第一次参加信息学奥赛时我遇到了一道看似简单却暗藏玄机的排序题——OpenJudge 1.10-06整数奇偶排序。题目要求将10个整数按奇数在前降序、偶数在后升序排列。当时我花了整整一小时才写出正确的比较函数而邻座的同学只用了几分钟。这个经历让我深刻认识到掌握STL sort函数的自定义排序技巧是算法竞赛中事半功倍的关键。1. 题目解析与基础解法OpenJudge 1.10-06题目描述很简单给定10个整数要求奇数在前按降序排列偶数在后按升序排列。例如输入1 2 3 4 5 6 7 8 9 10输出应为9 7 5 3 1 2 4 6 8 10。1.1 分治策略奇偶分离排序最直观的思路是将奇数和偶数分离到两个数组分别排序后再合并。这种方法逻辑清晰适合初学者理解#include bits/stdc.h using namespace std; void separateSort() { vectorint odds, evens; for(int i 0; i 10; i) { int num; cin num; (num % 2 ? odds : evens).push_back(num); } sort(odds.begin(), odds.end(), greaterint()); sort(evens.begin(), evens.end()); for(int x : odds) cout x ; for(int x : evens) cout x ; }优点逻辑简单直接两种排序规则完全分离不易混淆调试时容易定位问题缺点需要额外空间存储两个数组合并步骤增加了代码量不适用于需要保持原序列相对顺序的场景1.2 统一比较函数单次排序的优雅实现进阶解法是设计一个统一的比较函数通过一次sort调用完成排序bool customCompare(int a, int b) { bool aOdd a % 2, bOdd b % 2; if(aOdd bOdd) return a b; // 都是奇数则降序 if(!aOdd !bOdd) return a b; // 都是偶数则升序 return aOdd !bOdd; // 奇前偶后 } void unifiedSort() { vectorint nums(10); for(int x : nums) cin x; sort(nums.begin(), nums.end(), customCompare); for(int x : nums) cout x ; }提示比较函数返回true表示a应该排在b前面这与数学上的小于关系概念不同需要特别注意。2. 比较函数设计的深层原理STL sort函数使用的是一种混合排序算法通常是快速排序插入排序其核心在于元素间的比较操作。理解比较函数的运作机制对编写高效正确的排序逻辑至关重要。2.1 严格弱序与比较函数规范一个合法的比较函数必须满足以下数学性质非自反性cmp(a,a)必须为false非对称性如果cmp(a,b)为true则cmp(b,a)必须为false传递性如果cmp(a,b)和cmp(b,c)都为true则cmp(a,c)也必须为true违反这些规则会导致未定义行为常见错误包括// 错误示例1不满足非自反性 bool wrong1(int a, int b) { return a b; } // 错误示例2不满足传递性 bool wrong2(int a, int b) { if(abs(a-b) 5) return a b; return false; }2.2 比较函数的性能优化在竞赛中比较函数的执行效率直接影响程序性能。优化技巧包括减少模运算奇偶判断可以优化为位运算bool aOdd a 1; // 比a%2更快提前返回利用短路求值特性bool cmp(int a, int b) { bool aOdd a 1, bOdd b 1; if(aOdd ! bOdd) return aOdd; return aOdd ? a b : a b; }避免重复计算缓存中间结果bool cmp(int a, int b) { static auto getKey [](int x) { return tuplebool, int(x%2, x%2 ? -x : x); }; return getKey(a) getKey(b); }3. 工程实践中的扩展应用实际编程中复杂的排序需求比比皆是。掌握自定义排序技巧能大幅提升代码质量。3.1 多条件排序的通用模式当需要按多个字段排序时可以采用tuple的字典序比较struct Student { string name; int score; bool isPass; }; void sortStudents(vectorStudent students) { sort(students.begin(), students.end(), [](const auto a, const auto b) { return tie(b.isPass, b.score, a.name) tie(a.isPass, a.score, b.name); // 先按是否通过降序再按分数降序最后按姓名升序 }); }3.2 非数值数据的排序技巧对于复杂对象可以提取排序键值而非直接比较对象struct Task { int priority; time_t deadline; string description; }; void scheduleTasks(vectorTask tasks) { sort(tasks.begin(), tasks.end(), [](const auto a, const auto b) { return make_pair(-a.priority, a.deadline) make_pair(-b.priority, b.deadline); }); }3.3 稳定性与特殊需求处理STL的sort是不稳定排序当需要保持相等元素的原始顺序时应使用stable_sortvectorpairint, string records; // 按分数降序排序同分者保持输入顺序 void sortRecords() { stable_sort(records.begin(), records.end(), [](const auto a, const auto b) { return a.first b.first; }); }4. 竞赛中的实战技巧与陷阱规避算法竞赛中排序相关的题目往往考察选手对边界条件的处理能力和代码实现的精确度。4.1 常见错误案例分析比较函数不一致// 危险当a和b相等时可能返回true bool riskyCompare(int a, int b) { if(a%2 ! b%2) return a%2; return a%2 ? a b : a b; }修改外部状态的比较函数int counter 0; bool badCompare(int a, int b) { counter; // 错误比较函数不应有副作用 return a b; }浮点数比较的精度问题vectordouble nums; // 错误浮点数直接比较可能因精度丢失导致问题 sort(nums.begin(), nums.end(), [](double a, double b) { return a b; });4.2 调试与测试策略为确保排序正确性建议单元测试用例设计全奇数/全偶数序列已排序/逆序序列包含重复元素的序列边界值如INT_MIN, INT_MAX可视化调试技巧void debugSort(vectorint nums) { auto orig nums; sort(nums.begin(), nums.end(), customCompare); cout Before: ; for(int x : orig) cout x ; cout \nAfter: ; for(int x : nums) cout x ; }使用assert验证不变量void testCompare() { assert(!customCompare(1,1)); assert(customCompare(3,1)); assert(!customCompare(2,4)); assert(customCompare(1,2)); assert(!customCompare(2,1)); }4.3 性能优化实战对于大规模数据排序可以考虑减少比较操作开销// 预先计算排序键值 vectorint nums; vectorpairbool, int keys; for(int x : nums) keys.emplace_back(x%2, x%2 ? -x : x); sort(nums.begin(), nums.end(), [](int a, int b) { return keys[a] keys[b]; });利用数据特性选择算法小规模数据n30插入排序可能更快几乎有序数据考虑使用自适应排序有范围限制的整数计数排序/基数排序更优并行化排序#include execution sort(execution::par, nums.begin(), nums.end());在NOI等竞赛中我曾见过选手因为忽略比较函数的严格弱序要求而丢失整题分数也见过巧妙利用自定义排序将O(n²)算法优化到O(nlogn)的精彩解法。真正掌握STL sort的自定义排序不仅能解决像OpenJudge 1.10-06这样的基础题目更能应对各种复杂的现实排序需求。