C++竞赛刷题：用STL sort函数搞定OpenJudge 1.10-06整数奇偶排序（附两种思路对比）-程序员充电站

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() { vector<int> 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(), greater<int>()); 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() { vector<int> 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 tuple<bool, 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(vector<Student>& 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(vector<Task>& 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_sort：

vector<pair<int, 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; }

浮点数比较的精度问题：

vector<double> nums; // 错误：浮点数直接比较可能因精度丢失导致问题 sort(nums.begin(), nums.end(), [](double a, double b) { return a < b; });

4.2 调试与测试策略

为确保排序正确性，建议：

单元测试用例设计：
- 全奇数/全偶数序列
- 已排序/逆序序列
- 包含重复元素的序列
- 边界值（如INT_MIN, INT_MAX）

可视化调试技巧：

void debugSort(vector<int>& 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 性能优化实战

对于大规模数据排序，可以考虑：

减少比较操作开销：

// 预先计算排序键值 vector<int> nums; vector<pair<bool, 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]; });

利用数据特性选择算法：
- 小规模数据（n<30）：插入排序可能更快
- 几乎有序数据：考虑使用自适应排序
- 有范围限制的整数：计数排序/基数排序更优

并行化排序：

#include <execution> sort(execution::par, nums.begin(), nums.end());

在NOI等竞赛中，我曾见过选手因为忽略比较函数的严格弱序要求而丢失整题分数，也见过巧妙利用自定义排序将O(n²)算法优化到O(nlogn)的精彩解法。真正掌握STL sort的自定义排序，不仅能解决像OpenJudge 1.10-06这样的基础题目，更能应对各种复杂的现实排序需求。

C++竞赛刷题：用STL sort函数搞定OpenJudge 1.10-06整数奇偶排序（附两种思路对比）