从一道OpenJudge排序题，聊聊C++自定义排序的几种写法与选择（附整数奇偶排序完整代码）-程序员充电站

从一道OpenJudge排序题，聊聊C++自定义排序的几种写法与选择

在信息学竞赛和算法练习中，排序是最基础也最常被考察的操作之一。OpenJudge和NOI等平台上的排序题目往往不只是测试学生对标准排序算法的掌握，更考验他们根据特定规则自定义排序逻辑的能力。整数奇偶排序就是这样一个典型问题——它要求将奇数降序排列在前，偶数升序排列在后。这道看似简单的题目背后，隐藏着C++自定义排序的多种实现方式和设计哲学。

1. 理解自定义排序的核心需求

自定义排序的本质是定义元素间的"序关系"。在标准排序中，我们通常使用数值大小或字典序作为比较基准。但当面对像整数奇偶排序这样的特殊需求时，我们需要构建一个符合题目要求的比较规则。

对于整数奇偶排序问题，规则可以分解为：

奇数和偶数之间的比较：奇数始终排在偶数前面
奇数之间的比较：数值大的排在前面（降序）
偶数之间的比较：数值小的排在前面（升序）

这种多层次的比较逻辑正是自定义排序的典型场景。在C++中，我们主要通过三种方式实现这种自定义排序：

传统比较函数
逻辑运算符组合的简洁写法
Lambda表达式

每种方法各有优劣，适用于不同场景。下面我们将深入探讨这三种实现方式。

2. 传统比较函数实现

传统比较函数是最直观的实现方式，使用if-else分支明确处理各种情况：

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; // 奇数在前 } }

这种写法的优势在于：

可读性强：逻辑分支清晰，易于理解
可维护性好：修改或添加新规则时容易定位
调试方便：可以单独测试每个条件分支

但它的缺点是代码量相对较大，特别是在简单比较规则时显得冗长。这种写法特别适合：

复杂的多条件排序规则
需要长期维护的代码
团队协作项目

3. 逻辑运算符组合的简洁写法

对于追求代码简洁的竞赛选手，常常会使用逻辑运算符组合来实现同样的功能：

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); }

这种写法的特点包括：

代码紧凑：通常只需一行即可表达完整逻辑
执行效率高：减少了分支判断的开销
竞赛友好：适合快速编码的场景

但它的缺点也很明显：

可读性差：逻辑不易一眼看明白
维护困难：修改时需要重新理解整个表达式
调试麻烦：难以单独测试某一部分逻辑

这种写法最适合：

时间紧迫的编程竞赛
简单且稳定的排序规则
个人使用的临时代码

4. Lambda表达式的现代C++写法

C++11引入的Lambda表达式为自定义排序提供了更灵活的解决方案：

sort(a, a+n, [](int a, int b) { if(a%2 == b%2) { return a%2 ? a > b : a < b; } return a%2; });

Lambda表达式的优势在于：

就地定义：不需要单独写比较函数
灵活性高：可以捕获外部变量
现代风格：符合C++11及以后的标准
可读性适中：比运算符组合更清晰

它的适用场景包括：

只需要一次性使用的比较逻辑
需要访问外部变量的排序场景
现代C++代码库

5. 性能与可读性的权衡

在实际应用中，我们需要根据场景在不同实现间做出选择。下表对比了三种方法的特性：

特性	传统比较函数	逻辑运算符组合	Lambda表达式
代码量	多	少	中等
可读性	高	低	中等
维护性	好	差	中等
执行效率	中等	高	中等
适用场景	工程代码	竞赛代码	现代C++项目

在信息学竞赛中，选手通常更倾向于使用逻辑运算符组合或Lambda表达式，以节省编码时间。而在实际工程项目中，传统比较函数因其更好的可读性和可维护性而更受青睐。

6. 完整代码实现与测试

下面提供一个使用Lambda表达式的完整解决方案，并添加了测试用例：

#include <iostream> #include <algorithm> using namespace std; void oddEvenSort(int arr[], int n) { sort(arr, arr+n, [](int a, int b) { if((a & 1) && (b & 1)) { // 都是奇数 return a > b; // 降序 } else if(!(a & 1) && !(b & 1)) { // 都是偶数 return a < b; // 升序 } else { // 一奇一偶 return (a & 1); // 奇数在前 } }); } int main() { int arr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int n1 = sizeof(arr1)/sizeof(arr1[0]); oddEvenSort(arr1, n1); for(int x : arr1) cout << x << " "; // 输出: 9 7 5 3 1 2 4 6 8 10 cout << endl; int arr2[] = {4, 2, 8, 6, 10, 1, 3, 5, 7, 9}; int n2 = sizeof(arr2)/sizeof(arr2[0]); oddEvenSort(arr2, n2); for(int x : arr2) cout << x << " "; // 输出: 9 7 5 3 1 2 4 6 8 10 return 0; }

这段代码展示了：

使用Lambda表达式实现自定义排序
位运算优化奇偶判断（a & 1比a%2更高效）
模块化设计（将排序封装为函数）
测试用例验证

7. 扩展思考：更复杂的排序规则

掌握了基本实现后，我们可以考虑更复杂的排序场景。例如：

三部分排序：负数升序在前，然后零，最后正数降序
多关键字排序：先按字符串长度，再按字典序
自定义对象排序：按对象的某个成员变量排序

这些场景都可以通过适当修改比较函数来实现。关键在于清晰地定义比较规则，并选择适合的实现方式。

在工程实践中，当排序规则变得非常复杂时，可以考虑以下策略：

将比较逻辑分解为多个辅助函数
使用策略模式封装不同的排序规则
为自定义对象重载比较运算符

8. 实际应用中的注意事项

在实际使用自定义排序时，有几个常见陷阱需要注意：

严格弱序规则：比较函数必须满足严格弱序，即：
- 非自反性：comp(a,a)必须为false
- 非对称性：如果comp(a,b)为true，则comp(b,a)必须为false
- 可传递性：如果comp(a,b)和comp(b,c)为true，则comp(a,c)必须为true
性能考虑：比较函数会被频繁调用，应避免：
- 复杂的计算
- 耗时的操作（如I/O、内存分配）
- 重复计算（可将结果缓存）
可维护性：
- 为复杂比较函数添加注释
- 考虑使用命名常量代替魔术数字
- 保持一致的代码风格