信息学奥赛刷题实战：用C++ STL sort函数搞定整数奇偶排序（附两种解法对比）

在信息学奥赛（NOI）和OpenJudge等编程竞赛中，排序算法是最基础也是最重要的技能之一。面对"整数奇偶排序"这类看似简单实则暗藏玄机的题目，如何写出既高效又优雅的代码，往往是区分新手和老手的关键。本文将带你深入探讨如何利用C++ STL中的sort函数，通过自定义比较规则来巧妙解决这类复合排序问题。

1. 理解题目需求与挑战

整数奇偶排序题目通常要求将一组整数按照特定规则排序：所有奇数排在偶数前面，奇数之间按降序排列，偶数之间按升序排列。这种复合排序条件看似简单，但在实际编码中却可能遇到各种陷阱。

常见新手误区 ：

• 试图一次性完成所有排序条件
• 忽略比较函数的严格弱序要求
• 对STL sort函数的理解不够深入

让我们先看一个典型输入输出示例：

输入：1 2 3 4 5 6 7 8 9 10
输出：9 7 5 3 1 2 4 6 8 10

2. 解法一：分而治之策略

第一种思路是将奇数和偶数分开处理，分别排序后再合并。这种方法直观易懂，特别适合初学者理解。

2.1 实现步骤

1. 分离奇偶数 ：遍历输入数组，将奇数存入odd数组，偶数存入even数组
2. 分别排序 ：
   • 对odd数组进行降序排序
   • 对even数组进行升序排序
3. 合并输出 ：先输出排序后的odd数组，再输出even数组

#include <bits/stdc++.h>
using namespace std;

bool cmpDown(int a, int b) { return a > b; } // 降序比较
bool cmpUp(int a, int b) { return a < b; }   // 升序比较

int main() {
    int num, odd[15], even[15], oi = 0, ei = 0;
    
    for(int i = 0; i < 10; ++i) {
        cin >> num;
        if(num % 2) odd[oi++] = num;
        else even[ei++] = num;
    }
    
    sort(odd, odd + oi, cmpDown);
    sort(even, even + ei, cmpUp);
    
    for(int i = 0; i < oi; ++i) cout << odd[i] << ' ';
    for(int i = 0; i < ei; ++i) cout << even[i] << ' ';
    
    return 0;
}

2.2 优缺点分析

优势 ：

• 逻辑清晰，易于理解和调试
• 适合教学和初学者练习
• 对排序算法的稳定性要求较低

劣势 ：

• 需要额外的存储空间
• 需要进行两次排序操作
• 代码量相对较大

3. 解法二：统一排序策略

更高级的解法是设计一个统一的比较函数，一次性完成所有排序条件。这种方法更能体现对STL sort函数的深入理解。

3.1 比较函数设计

关键点在于设计一个满足严格弱序的比较函数，同时实现：

1. 奇数优先于偶数
2. 奇数之间降序排列
3. 偶数之间升序排列

#include <bits/stdc++.h>
using namespace std;

bool cmp(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;                      // 一奇一偶，奇数在前
}

int main() {
    int nums[10];
    for(int i = 0; i < 10; ++i) cin >> nums[i];
    
    sort(nums, nums + 10, cmp);
    
    for(int i = 0; i < 10; ++i) cout << nums[i] << ' ';
    
    return 0;
}

3.2 代码优化技巧

可以将比较函数进一步简化为单行表达式：

bool cmp(int a, int b) {
    return (a%2 == b%2) ? (a%2 ? a>b : a<b) : a%2;
}

注意事项 ：

• 确保比较函数满足严格弱序
• 避免在比较函数中进行复杂计算
• 考虑边界情况（如负数、零值）

4. 两种解法的性能对比

虽然题目数据量较小（仅10个数字），但了解不同解法的性能特点对培养算法思维很有帮助。

对比项	分而治之法	统一排序法
时间复杂度	O(2nlogn)	O(nlogn)
空间复杂度	O(n)	O(1)
代码简洁性	中等	优秀
可读性	高	中等
扩展性	低	高

实际应用建议 ：

• 教学场景：优先使用分而治之法
• 竞赛场景：推荐统一排序法
• 大型数据集：统一排序法优势明显

5. 常见错误与调试技巧

在实现这类复合排序时，容易遇到一些典型错误：

5.1 比较函数不符合严格弱序

错误的比较函数可能导致程序崩溃或排序结果异常。例如：

// 错误示例：不满足严格弱序
bool bad_cmp(int a, int b) {
    if(a % 2 != b % 2) return a % 2;
    return true; // 违反反对称性
}

调试技巧 ：

• 使用简单测试用例验证
• 检查比较函数的三个性质：非自反性、反对称性、传递性

5.2 数组索引处理不当

初学者常犯的数组索引错误：

// 错误示例：1-based索引与0-based索引混用
for(int i = 1; i <= 10; ++i) {
    cin >> nums[i]; // 可能越界
}
sort(nums + 1, nums + 11, cmp); // 长度计算错误

最佳实践 ：

• 统一使用0-based索引
• 使用vector容器替代原生数组
• 添加边界检查

6. 进阶思考与扩展

掌握了基础解法后，可以进一步思考：

6.1 使用lambda表达式

C++11引入的lambda表达式可以让代码更简洁：

sort(nums, nums + 10, [](int a, int b) {
    bool aOdd = a % 2, bOdd = b % 2;
    return aOdd != bOdd ? aOdd : aOdd ? a > b : a < b;
});

6.2 处理更大数据量

当数据量增大时，可以考虑：

• 使用更高效的排序算法
• 并行化排序过程
• 优化比较函数的执行效率

6.3 扩展到其他复合排序场景

类似的思路可以应用于：

• 多关键字排序
• 自定义对象排序
• 混合类型数据排序

7. 实战演练与测试用例

为了确保代码的正确性，应该设计全面的测试用例：

测试用例设计 ：

1. 全奇数情况
2. 全偶数情况
3. 混合情况
4. 包含负数的情况
5. 包含零的情况
6. 重复数字情况
7. 边界值测试（最大最小值）

示例测试代码：

void test_sort() {
    vector<vector<int>> test_cases = {
        {1,3,5,7,9,2,4,6,8,10}, // 标准情况
        {1,1,1,1,1,2,2,2,2,2},  // 重复数字
        {-3,-1,0,2,4,-5,-7,6,8,10}, // 含负数
        {0,0,0,0,0,0,0,0,0,0},  // 全零
        {INT_MAX, INT_MIN, 0, -1, 1, 2, -2, 3, -3, 4} // 边界值
    };
    
    for(auto &tc : test_cases) {
        sort(tc.begin(), tc.end(), cmp);
        // 验证排序结果...
    }
}

8. 竞赛中的实用技巧

在实际竞赛中，除了正确性，还需要考虑编码效率和调试便利性：

实用技巧 ：

1. 预先编写常用排序比较函数模板
2. 使用宏定义简化代码
3. 添加调试输出语句（比赛时记得删除）
4. 准备常用测试用例函数
5. 熟悉STL算法的各种应用场景

// 调试输出示例
#define debug(x) cerr << #x << " = " << x << endl

void debug_print(const vector<int>& v) {
    cerr << "当前数组: ";
    for(int num : v) cerr << num << ' ';
    cerr << endl;
}

9. 性能优化深入探讨

虽然题目数据量小，但了解性能优化对培养算法思维很重要：

9.1 比较函数优化

比较函数的执行效率直接影响排序性能：

// 优化后的比较函数
bool optimized_cmp(int a, int b) {
    int aMod = a % 2, bMod = b % 2;
    return (aMod ^ bMod) ? aMod : aMod ? a > b : a < b;
}

9.2 算法选择策略

根据数据特点选择算法：

• 小数据量：插入排序可能更快
• 部分有序数据：考虑适应性排序算法
• 内存受限环境：选择原地排序算法

9.3 缓存友好性

考虑数据局部性原理：

• 连续内存访问更高效
• 减少分支预测失败
• 避免不必要的内存分配

10. 从题目到竞赛思维的提升

解决这类排序问题不仅是写出正确代码，更要培养竞赛思维：

思维要点 ：

1. 问题分解能力：将复杂条件拆解为简单规则
2. STL深度应用：充分利用标准库功能
3. 边界情况考虑：全面思考各种可能输入
4. 性能评估意识：即使小数据量也要考虑算法效率
5. 代码简洁性：在保证可读性的前提下追求简洁

在实际竞赛中，这类排序问题往往只是更大问题的组成部分。培养快速准确解决基础问题的能力，才能在面对复杂问题时游刃有余。