信息学奥赛刷题笔记：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; }这种方法有几个关键点需要注意数组下标从0开始更符合C常规用法使用STL的sort函数可以大幅简化排序实现需要正确定义升序和降序的比较函数提示在实际竞赛中使用标准库函数通常比手写排序更可靠且不易出错除非题目明确要求实现特定排序算法。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 比较函数设计原理这个自定义比较函数的设计体现了排序问题的核心逻辑奇偶优先通过比较a%2 b%2确保奇数始终排在偶数前面奇数降序当两个数都是奇数时返回a b实现降序偶数升序当两个数都是偶数时返回a b实现升序这种方法的优势在于只需要一次排序操作不需要额外的存储空间代码更加简洁优雅更容易扩展到更复杂的排序规则3. 两种解法的性能对比虽然题目数据量很小仅10个数但了解不同解法的性能特点对算法学习很有帮助。对比维度分组排序法自定义比较函数法时间复杂度O(n log n) × 2O(n log n)空间复杂度O(n)O(1)代码复杂度中等较高扩展性一般优秀适用场景规则简单的复合排序规则复杂的复合排序从表中可以看出自定义比较函数法在大多数方面都优于分组排序法特别是当排序规则变得更加复杂时。4. 常见错误与调试技巧4.1 新手易犯的错误数组下标混淆有些教材使用1-based索引而C默认是0-based比较函数逻辑错误特别是复合条件的优先级问题奇偶判断不严谨负数取模在不同语言中结果可能不同输出格式不符末尾多余空格或缺少空格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[(leftright)/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 实际应用场景这类复合排序在实际开发中很常见例如电商商品排序销量评分价格学生成绩排名总分单科成绩任务调度优先级紧急程度截止时间