信息学奥赛刷题笔记用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 121.2 解题思路概览面对这样的排序需求我们可以考虑两种主要思路分而治之将奇数和偶数分离到两个不同的数组分别排序后再合并统一规则设计一个比较函数一次性完成所有元素的排序这两种方法各有优劣理解它们的差异对于提升算法设计能力至关重要。2. 分数组排序法详解2.1 基本实现步骤分数组排序法的核心思想是将问题分解为几个更简单的子问题数据分离遍历输入数组将奇数和偶数分别存入两个不同的数组独立排序对奇数数组进行降序排序对偶数数组进行升序排序结果合并先输出排序后的奇数数组再输出排序后的偶数数组#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 自定义比较函数设计统一比较规则法的核心在于设计一个能够同时满足三种情况的比较函数奇偶性不同时奇数应该排在偶数前面同为奇数时数值大的排在前面降序同为偶数时数值小的排在前面升序#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) × 2O(n log n)空间复杂度O(n)O(1)排序次数2次1次代码复杂度简单较复杂可扩展性一般更好4.2 适用场景分析分数组排序法更适合初学者理解题目需求需要分别处理奇偶数据的情况当奇偶数的后续处理逻辑不同时统一比较规则法更适合追求代码简洁和效率需要一次性完成排序的场景作为更复杂排序规则的基础4.3 竞赛中的实用建议在实际竞赛中建议根据以下因素选择方法题目复杂度如果排序规则简单优先考虑统一比较规则时间压力在时间紧张时选择你最熟悉的方法后续需求如果需要分别处理奇偶数分数组可能更方便调试难度分数组方法更容易单独测试和调试5. 常见错误与调试技巧5.1 典型错误案例奇偶判断错误错误写法if(num % 2 1)对负数无效正确写法if(num % 2 ! 0)数组索引错误从0开始还是从1开始要统一数组大小要足够本题至少10个元素比较函数逻辑错误没有正确处理三种情况返回值的含义混淆true表示a应该在b前面5.2 调试方法小数据测试使用题目样例和自编简单案例边界测试全奇数、全偶数、包含负数等情况打印中间结果在关键步骤输出变量值逐步验证先验证奇偶分离再验证各自排序// 调试示例打印中间结果 void debug_print(int arr[], int n) { cout Debug: ; for(int i 0; i n; i) cout arr[i] ; cout endl; }6. 扩展思考与变式训练6.1 类似题目推荐多条件排序如先按绝对值排序再按正负分开多关键字排序如先按成绩降序同分按姓名升序自定义结构体排序对复杂数据类型的排序6.2 算法思想延伸STL的强大功能除了sort还有stable_sort、partial_sort等Lambda表达式C11后可以直接在sort中使用lambda性能优化对于特定数据可以考虑非比较排序算法// 使用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; });在实际刷题过程中我发现理解排序规则的本质比记忆代码模板更重要。这道题目虽然简单但它教会我们如何将复杂需求分解为可实现的比较逻辑。当遇到更复杂的排序问题时这种分析能力将发挥巨大作用。
信息学奥赛刷题笔记：用C++ STL sort函数搞定OpenJudge 1.10-06整数奇偶排序（两种思路详解）
信息学奥赛刷题笔记用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 121.2 解题思路概览面对这样的排序需求我们可以考虑两种主要思路分而治之将奇数和偶数分离到两个不同的数组分别排序后再合并统一规则设计一个比较函数一次性完成所有元素的排序这两种方法各有优劣理解它们的差异对于提升算法设计能力至关重要。2. 分数组排序法详解2.1 基本实现步骤分数组排序法的核心思想是将问题分解为几个更简单的子问题数据分离遍历输入数组将奇数和偶数分别存入两个不同的数组独立排序对奇数数组进行降序排序对偶数数组进行升序排序结果合并先输出排序后的奇数数组再输出排序后的偶数数组#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 自定义比较函数设计统一比较规则法的核心在于设计一个能够同时满足三种情况的比较函数奇偶性不同时奇数应该排在偶数前面同为奇数时数值大的排在前面降序同为偶数时数值小的排在前面升序#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) × 2O(n log n)空间复杂度O(n)O(1)排序次数2次1次代码复杂度简单较复杂可扩展性一般更好4.2 适用场景分析分数组排序法更适合初学者理解题目需求需要分别处理奇偶数据的情况当奇偶数的后续处理逻辑不同时统一比较规则法更适合追求代码简洁和效率需要一次性完成排序的场景作为更复杂排序规则的基础4.3 竞赛中的实用建议在实际竞赛中建议根据以下因素选择方法题目复杂度如果排序规则简单优先考虑统一比较规则时间压力在时间紧张时选择你最熟悉的方法后续需求如果需要分别处理奇偶数分数组可能更方便调试难度分数组方法更容易单独测试和调试5. 常见错误与调试技巧5.1 典型错误案例奇偶判断错误错误写法if(num % 2 1)对负数无效正确写法if(num % 2 ! 0)数组索引错误从0开始还是从1开始要统一数组大小要足够本题至少10个元素比较函数逻辑错误没有正确处理三种情况返回值的含义混淆true表示a应该在b前面5.2 调试方法小数据测试使用题目样例和自编简单案例边界测试全奇数、全偶数、包含负数等情况打印中间结果在关键步骤输出变量值逐步验证先验证奇偶分离再验证各自排序// 调试示例打印中间结果 void debug_print(int arr[], int n) { cout Debug: ; for(int i 0; i n; i) cout arr[i] ; cout endl; }6. 扩展思考与变式训练6.1 类似题目推荐多条件排序如先按绝对值排序再按正负分开多关键字排序如先按成绩降序同分按姓名升序自定义结构体排序对复杂数据类型的排序6.2 算法思想延伸STL的强大功能除了sort还有stable_sort、partial_sort等Lambda表达式C11后可以直接在sort中使用lambda性能优化对于特定数据可以考虑非比较排序算法// 使用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; });在实际刷题过程中我发现理解排序规则的本质比记忆代码模板更重要。这道题目虽然简单但它教会我们如何将复杂需求分解为可实现的比较逻辑。当遇到更复杂的排序问题时这种分析能力将发挥巨大作用。
