信息学奥赛刷题笔记：用C++ STL sort函数搞定OpenJudge 1.10-06整数奇偶排序（两种思路详解）

在信息学奥赛的备战过程中，排序算法是最基础也是最重要的技能之一。OpenJudge 1.10-06的整数奇偶排序题目看似简单，却蕴含着丰富的算法设计思想。这道题目要求将10个整数按照奇数在前降序、偶数在后升序的顺序排列，考察了选手对排序规则的理解和实现能力。

对于初学者来说，这道题目最大的价值不在于写出正确的代码，而在于理解如何通过不同的思路解决同一个问题。本文将深入探讨两种主流解法：分数组排序和统一比较规则，分析它们的优缺点，并分享在实际竞赛中如何快速选择合适的方法。

1. 理解题目与需求分析

1.1 题目要求解析

题目给出10个整数，要求输出的顺序满足：

• 所有奇数出现在所有偶数之前
• 奇数部分按照从大到小的顺序排列
• 偶数部分按照从小到大的顺序排列

例如，输入序列： 4 7 3 13 12 2 15 6 8 5 正确输出应为： 15 13 7 5 3 2 4 6 8 12

1.2 解题思路概览

面对这样的排序需求，我们可以考虑两种主要思路：

1. 分而治之 ：将奇数和偶数分离到两个不同的数组，分别排序后再合并
2. 统一规则 ：设计一个比较函数，一次性完成所有元素的排序

这两种方法各有优劣，理解它们的差异对于提升算法设计能力至关重要。

2. 分数组排序法详解

2.1 基本实现步骤

分数组排序法的核心思想是将问题分解为几个更简单的子问题：

1. 数据分离 ：遍历输入数组，将奇数和偶数分别存入两个不同的数组
2. 独立排序 ：
   • 对奇数数组进行降序排序
   • 对偶数数组进行升序排序
3. 结果合并 ：先输出排序后的奇数数组，再输出排序后的偶数数组

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

bool cmp_odd(int a, int b) { return a > b; } // 奇数降序
bool cmp_even(int a, int b) { return a < b; } // 偶数升序

int main() {
    int num, odd[15], even[15], o_cnt = 0, e_cnt = 0;
    
    for(int i = 0; i < 10; ++i) {
        cin >> num;
        if(num % 2 == 0) even[e_cnt++] = num;
        else odd[o_cnt++] = num;
    }
    
    sort(odd, odd + o_cnt, cmp_odd);
    sort(even, even + e_cnt, cmp_even);
    
    for(int i = 0; i < o_cnt; ++i) cout << odd[i] << " ";
    for(int i = 0; i < e_cnt; ++i) cout << even[i] << " ";
    
    return 0;
}

2.2 方法优缺点分析

优点 ：

• 思路直观，容易理解和实现
• 两个排序过程相互独立，调试方便
• 代码结构清晰，可读性强

缺点 ：

• 需要额外的存储空间（两个数组）
• 需要进行两次排序操作
• 合并输出时需要额外处理

提示：在数据量较小（如本题的10个元素）时，这种方法的性能差异可以忽略不计，但在处理大规模数据时需要考虑空间和时间效率。

3. 统一比较规则法详解

3.1 自定义比较函数设计

统一比较规则法的核心在于设计一个能够同时满足三种情况的比较函数：

1. 奇偶性不同时 ：奇数应该排在偶数前面
2. 同为奇数时 ：数值大的排在前面（降序）
3. 同为偶数时 ：数值小的排在前面（升序）

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

bool cmp(int a, int b) {
    if(a % 2 != b % 2) return a % 2; // 奇偶不同，奇数在前
    if(a % 2) return a > b; // 都是奇数，降序
    return a < b; // 都是偶数，升序
}

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

3.2 比较函数优化技巧

我们可以通过逻辑运算简化比较函数：

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

或者更简洁的写法：

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

注意：虽然简洁的代码看起来很酷，但在实际竞赛中，可读性和正确性更为重要。建议先写出清晰易懂的版本，确保正确后再考虑优化。

4. 两种方法的对比与选择策略

4.1 性能对比

虽然本题数据量很小，两种方法性能差异不大，但从理论上分析：

对比维度	分数组排序法	统一比较规则法
时间复杂度	O(n log n) × 2	O(n log n)
空间复杂度	O(n)	O(1)
排序次数	2次	1次
代码复杂度	简单	较复杂
可扩展性	一般	更好

4.2 适用场景分析

分数组排序法更适合 ：

• 初学者理解题目需求
• 需要分别处理奇偶数据的情况
• 当奇偶数的后续处理逻辑不同时

统一比较规则法更适合 ：

• 追求代码简洁和效率
• 需要一次性完成排序的场景
• 作为更复杂排序规则的基础

4.3 竞赛中的实用建议

在实际竞赛中，建议根据以下因素选择方法：

1. 题目复杂度 ：如果排序规则简单，优先考虑统一比较规则
2. 时间压力 ：在时间紧张时，选择你最熟悉的方法
3. 后续需求 ：如果需要分别处理奇偶数，分数组可能更方便
4. 调试难度 ：分数组方法更容易单独测试和调试

5. 常见错误与调试技巧

5.1 典型错误案例

1. 奇偶判断错误 ：

   • 错误写法： if(num % 2 == 1) （对负数无效）
   • 正确写法： if(num % 2 != 0)

2. 数组索引错误 ：

   • 从0开始还是从1开始要统一
   • 数组大小要足够（本题至少10个元素）

3. 比较函数逻辑错误 ：

   • 没有正确处理三种情况
   • 返回值的含义混淆（true表示a应该在b前面）

5.2 调试方法

1. 小数据测试 ：使用题目样例和自编简单案例
2. 边界测试 ：全奇数、全偶数、包含负数等情况
3. 打印中间结果 ：在关键步骤输出变量值
4. 逐步验证 ：先验证奇偶分离，再验证各自排序

// 调试示例：打印中间结果
void debug_print(int arr[], int n) {
    cout << "Debug: ";
    for(int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;
}

6. 扩展思考与变式训练

6.1 类似题目推荐

1. 多条件排序 ：如先按绝对值排序，再按正负分开
2. 多关键字排序 ：如先按成绩降序，同分按姓名升序
3. 自定义结构体排序 ：对复杂数据类型的排序

6.2 算法思想延伸

1. STL的强大功能 ：除了sort，还有stable_sort、partial_sort等
2. Lambda表达式 ：C++11后可以直接在sort中使用lambda
3. 性能优化 ：对于特定数据，可以考虑非比较排序算法

// 使用lambda表达式的示例
sort(arr, arr + 10, [](int a, int b) {
    bool a_odd = a % 2, b_odd = b % 2;
    return a_odd != b_odd ? a_odd : a_odd ? a > b : a < b;
});

在实际刷题过程中，我发现理解排序规则的本质比记忆代码模板更重要。这道题目虽然简单，但它教会我们如何将复杂需求分解为可实现的比较逻辑。当遇到更复杂的排序问题时，这种分析能力将发挥巨大作用。