信息学奥赛刷题笔记：OpenJudge NOI 1.10 06题，我用两种思路搞定整数奇偶排序

信息学奥赛刷题笔记：OpenJudge NOI 1.10 06题，我用两种思路搞定整数奇偶排序

在信息学竞赛的刷题过程中，遇到排序类题目时，很多初学者往往只满足于实现基本功能，而忽略了多种解法的探索。今天我们就以OpenJudge NOI 1.10 06题"整数奇偶排序"为例，深入剖析两种截然不同的解题思路，帮助你在算法竞赛中培养灵活的思维方式。

1. 题目分析与基础解法

1.1 题目要求解析

题目要求对10个整数进行排序，排序规则为：

• 所有奇数排在偶数前面
• 奇数之间按从大到小排序
• 偶数之间按从小到大排序

这种复合排序规则在实际编程竞赛中很常见，它考察的是对排序算法的灵活运用能力。我们先来看最直观的解法——分组排序法。

1.2 分组排序法实现

分组排序法的核心思想是将奇数和偶数分离到两个不同的数组中，分别排序后再合并输出。这种方法思路清晰，适合初学者理解和实现。

#include <bits/stdc++.h> using namespace std; bool cmpUp(int a, int b) { return a < b; } // 升序比较函数 bool cmpDown(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 == 0) even[ei++] = num; // 存储偶数 else odd[oi++] = 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; }

这种方法有几个关键点需要注意：

1. 数组下标从0开始更符合C++常规用法
2. 使用STL的sort函数可以大幅简化排序实现
3. 需要正确定义升序和降序的比较函数

提示：在实际竞赛中，使用标准库函数通常比手写排序更可靠且不易出错，除非题目明确要求实现特定排序算法。

2. 进阶解法：自定义比较函数

2.1 单一排序的优雅实现

分组排序虽然直观，但需要额外的存储空间和两次排序操作。更优雅的解法是定义一个复合比较函数，通过一次排序完成所有要求。

#include <bits/stdc++.h> using namespace std; bool cmp(int a, int b) { if(a%2 != b%2) // 奇偶性不同 return a%2 > b%2; // 奇数排在前面 else if(a%2) // 都是奇数 return a > b; // 降序排列 else // 都是偶数 return a < b; // 升序排列 } 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; }

2.2 比较函数设计原理

这个自定义比较函数的设计体现了排序问题的核心逻辑：

1. 奇偶优先：通过比较a%2 > b%2确保奇数始终排在偶数前面
2. 奇数降序：当两个数都是奇数时，返回a > b实现降序
3. 偶数升序：当两个数都是偶数时，返回a < b实现升序

这种方法的优势在于：

• 只需要一次排序操作
• 不需要额外的存储空间
• 代码更加简洁优雅
• 更容易扩展到更复杂的排序规则

3. 两种解法的性能对比

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

从表中可以看出，自定义比较函数法在大多数方面都优于分组排序法，特别是当排序规则变得更加复杂时。

4. 常见错误与调试技巧

4.1 新手易犯的错误

1. 数组下标混淆：有些教材使用1-based索引，而C++默认是0-based
2. 比较函数逻辑错误：特别是复合条件的优先级问题
3. 奇偶判断不严谨：负数取模在不同语言中结果可能不同
4. 输出格式不符：末尾多余空格或缺少空格

4.2 调试建议

• 使用小规模测试数据验证边界条件
• 打印中间结果检查排序过程
• 单独测试比较函数的正确性
• 使用assert验证不变量

// 测试比较函数的示例 void test_cmp() { assert(cmp(3, 2) == true); // 奇>偶 assert(cmp(2, 3) == false); // 偶<奇 assert(cmp(5, 3) == true); // 奇>奇 assert(cmp(2, 4) == true); // 偶<偶 cout << "All test cases passed!" << endl; }

5. 算法扩展与应用

5.1 更复杂的排序规则

掌握了自定义比较函数的方法后，可以解决更复杂的排序问题，例如：

• 按照数字各位数之和排序
• 按照字符串的特殊规则排序
• 多关键字复合排序

5.2 其他排序算法实现

虽然STL的sort函数足够强大，但了解其他排序算法的实现也有助于深入理解排序原理。

使用快速排序实现：

void quickSort(int arr[], int left, int right, bool (*cmp)(int, int)) { if(left >= right) return; int pivot = arr[(left+right)/2]; int i = left, j = right; while(i <= j) { while(cmp(arr[i], pivot)) i++; while(cmp(pivot, arr[j])) j--; if(i <= j) swap(arr[i++], arr[j--]); } quickSort(arr, left, j, cmp); quickSort(arr, i, right, cmp); }

5.3 实际应用场景

这类复合排序在实际开发中很常见，例如：

• 电商商品排序（销量+评分+价格）
• 学生成绩排名（总分+单科成绩）
• 任务调度优先级（紧急程度+截止时间）