从一道OpenJudge排序题，聊聊C++自定义排序的几种写法（附奇偶排序完整代码）

深入解析C++自定义排序：从奇偶排序到高阶技巧

在算法竞赛和日常开发中，排序是最基础却最常被优化的操作之一。C++标准库中的sort函数因其高效和灵活性广受青睐，但真正发挥其威力的关键在于自定义比较函数的巧妙运用。本文将以OpenJudge经典的整数奇偶排序问题为切入点，系统剖析C++自定义排序的多种实现方式，并探讨其背后的设计哲学与性能考量。

1. 理解排序的本质与自定义比较

排序算法之所以能适应各种复杂场景，核心在于其可定制的比较逻辑。在C++中，std::sort默认使用<运算符进行升序排列，但通过自定义比较函数，我们可以实现任意规则的排序。

比较函数的基本原理：

bool cmp(const Type& a, const Type& b) { // 返回true表示a应该排在b前面 // 返回false表示b应该排在a前面 }

比较函数需要满足严格弱序（Strict Weak Ordering）的三个特性：

• 非自反性：cmp(a,a)必须为false
• 非对称性：若cmp(a,b)为true，则cmp(b,a)必须为false
• 传递性：若cmp(a,b)和cmp(b,c)为true，则cmp(a,c)必须为true

违反这些特性可能导致未定义行为，这是许多初学者容易踩的坑。

2. 奇偶排序的三种经典实现

2.1 分离数组法：最直观的实现

这种方法将奇数和偶数分别存储到不同数组，分别排序后再合并输出。虽然需要额外空间，但逻辑清晰，适合教学演示。

vector<int> odds, evens; for(int num : nums) { if(num % 2 != 0) odds.push_back(num); else evens.push_back(num); } sort(odds.begin(), odds.end(), greater<int>()); // 奇数降序 sort(evens.begin(), evens.end()); // 偶数升序 // 合并结果 odds.insert(odds.end(), evens.begin(), evens.end());

适用场景：

• 数据量不大，内存充足
• 需要保持代码高度可读性
• 后续可能需要对奇偶数列分别处理

2.2 单一比较函数：条件分支法

将所有排序规则整合到一个比较函数中，通过if-else结构明确表达每种情况的处理逻辑。

bool cmp(int a, int b) { if(a%2 && b%2) return a > b; // 都是奇数，大的在前 if(!(a%2) && !(b%2)) return a < b; // 都是偶数，小的在前 return a%2; // 一奇一偶，奇数在前 }

优势分析：

• 只需一次排序操作，效率更高
• 不占用额外内存空间
• 逻辑清晰，易于调试

在实际项目中，这种写法通常是最佳选择，平衡了性能和可读性。

2.3 逻辑运算符组合：简洁但晦涩

将多个条件用逻辑运算符组合，可以写出极其简洁但难以理解的比较函数。

bool cmp(int a, int b) { return (a%2 && b%2 && a > b) || (!(a%2) && !(b%2) && a < b) || (a%2 && !(b%2)); }

注意事项：

• 运算符优先级容易导致逻辑错误
• 可读性差，团队协作时不推荐
• 适合代码高尔夫等特殊场景

3. 现代C++的优雅解决方案

3.1 Lambda表达式：就地定义比较逻辑

C++11引入的lambda表达式让我们可以在调用sort时直接定义比较逻辑，代码更加紧凑。

sort(nums.begin(), nums.end(), [](int a, int b) { if(a%2 != b%2) return a%2 > b%2; return a%2 ? a > b : a < b; });

进阶技巧：

• 可以捕获外部变量（如配置参数）
• 支持泛型lambda（C++14起）
• 适合一次性使用的比较逻辑

3.2 结构化绑定与元组比较（C++17）

利用结构化绑定和元组的字典序比较，可以写出更函数式的代码。

sort(nums.begin(), nums.end(), [](int a, int b) { auto key = [](int x) { return make_tuple(!(x%2), x%2 ? -x : x); }; return key(a) < key(b); });

性能考虑：

• 虽然语法优雅，但可能产生临时对象
• 在性能敏感场景要谨慎使用
• 适合复杂多条件排序

4. 工程实践中的优化技巧

4.1 避免常见陷阱

错误示例1：违反严格弱序

// 错误：当a和b相等时会返回true bool cmp(int a, int b) { return a <= b; }

错误示例2：性能陷阱

// 每次比较都计算平方，性能低下 bool cmp(int a, int b) { return a*a < b*b; }

4.2 利用缓存优化

对于计算复杂的比较条件，可以预计算并缓存关键值。

vector<pair<bool, int>> decorated; for(int num : nums) { decorated.emplace_back(num%2==0, num); } sort(decorated.begin(), decorated.end(), [](auto& a, auto& b) { if(a.first != b.first) return !a.first; return a.first ? a.second < b.second : a.second > b.second; });

4.3 多条件排序的通用模式

对于需要按多个字段排序的场景，可以采用分层比较模式：

bool cmp(const Data& a, const Data& b) { if(a.field1 != b.field1) return a.field1 < b.field1; if(a.field2 != b.field2) return a.field2 > b.field2; return a.field3 < b.field3; }

5. 性能对比与选型建议

我们通过基准测试比较不同方法的性能（测试环境：100,000个随机整数）：

选型指南：

1. 教学/演示场景：优先选择分离数组法或条件分支法
2. 生产环境：推荐条件分支法或Lambda表达式
3. 性能极致优化：考虑逻辑运算符组合（需充分注释）
4. 复杂条件排序：元组比较法或装饰-排序-去装饰模式

在实际项目中，除了性能外，还应考虑代码的可维护性和团队成员的熟悉程度。过度优化往往得不偿失，清晰的代码逻辑比微小的性能提升更有价值。