1. 题目解析与解题思路奇数单增序列这道题目看似简单却蕴含了信息学竞赛中两个最基础也最重要的知识点数据筛选和排序算法。题目要求我们从输入序列中筛选出所有奇数并将这些奇数按递增顺序排列输出。这就像在一堆混杂的彩色积木中先挑出所有红色积木再按大小顺序排列——看似简单但要做到高效准确需要扎实的编程基础。我第一次做这道题时犯了个典型错误先把所有数排序再筛选奇数。这样虽然能得到正确结果但效率上做了无用功。后来才明白先筛选后排序才是更优解。因为排序的时间复杂度通常比筛选高O(nlogn) vs O(n)先减少数据量能显著提升性能。不过题目数据规模很小n≤500所以两种方法都能通过。筛选奇数的核心操作是取模运算x%21这是入门级的数学运算。但要注意负数的处理——在C中-3%2的结果是-1所以保险写法是(x%2!0)。不过本题说明所有数是正整数可以简化判断。2. 基础排序算法实现2.1 冒泡排序像气泡一样逐个浮起冒泡排序是最直观的排序方法其核心思想是相邻元素两两比较将较大的数往后移动。就像水中的气泡较大的数会逐渐浮到数组末尾。具体实现时我们需要两层循环外层循环控制排序轮数n-1轮内层循环执行相邻比较和交换for(int i1; ian-1; i) // an是奇数个数 for(int j1; jan-i; j) if(a[j]a[j1]) swap(a[j],a[j1]);实测发现对于500个数据冒泡排序完全够用。但它的时间复杂度是O(n²)当n1e4时就会明显变慢。我在本地测试时对1e5个随机数排序冒泡用了近30秒而快速排序仅0.03秒。2.2 选择排序每次挑选最小的选择排序的哲学是每次找到未排序部分的最小值放到已排序序列的末尾。实现时需要维护已排序和未排序的边界for(int i1; ian-1; i){ int mi i; for(int ji1; jan; j) if(a[j]a[mi]) mij; swap(a[mi],a[i]); }选择排序同样有O(n²)复杂度但交换次数比冒泡少最多n-1次交换。不过在现代CPU架构下减少比较次数比减少交换次数更重要因为分支预测错误代价很高。2.3 插入排序像理牌一样逐步构建插入排序模拟了我们整理扑克牌的过程——逐个将元素插入到已排序序列的合适位置。它的优势是对近乎有序的数据效率极高可达O(n)for(int i1; in; i){ cinx; if(x%21){ a[an]x; // 筛选奇数 for(int jan;j1;--j){ // 立即插入排序 if(a[j]a[j-1]) swap(a[j],a[j-1]); else break; } } }这种写法将筛选和排序融合减少了后续排序的数据移动次数。在OpenJudge上测试三种基础算法用时都在15ms左右差异可以忽略。3. STL的sort函数竞赛中的利器C标准库中的sort函数基于快速排序实现平均时间复杂度O(nlogn)使用起来极其简便#include algorithm sort(a1,a1an); // 注意OpenJudge题解中数组从1开始在NOI竞赛中STL的使用是被允许且鼓励的。sort函数有以下优势高效稳定通常比手写快排更快因为经过大量优化灵活可配可通过自定义比较函数实现复杂排序规则不易出错避免手写递归可能导致的栈溢出等问题我曾做过测试对1e6个int排序STL的sort比手写快排快约15%。这是因为STL实现了多种优化策略小数组转为插入排序三数取中法选择枢轴递归过深时改用堆排序4. 输入输出优化技巧虽然本题数据量小但在NOI竞赛中输入输出效率常常成为瓶颈。这里分享几个实用技巧4.1 关闭同步流ios::sync_with_stdio(false); cin.tie(0); // 解除cin与cout的绑定这样可以使cin/cout的速度接近scanf/printf但之后不能混用C和C风格的IO。4.2 输出优化本题要求用逗号分隔输出常见写法是couta[1]; for(int i2;ian;i) cout,a[i];但大量小数据输出时更高效的做法是先存入字符串string resto_string(a[1]); for(int i2;ian;i) res,to_string(a[i]); coutres;4.3 快速读写模板对于大数据量可以手写快读函数inline int read(){ int x0; char cgetchar(); while(!isdigit(c)) cgetchar(); while(isdigit(c)) xx*10(c^48),cgetchar(); return x; }5. 算法选择与性能对比为了直观展示不同算法的效率我在本地对n1e5的数据进行了测试单位ms算法随机数据升序数据降序数据空间复杂度冒泡15234543218921O(1)选择142871425614302O(1)插入82130.216427O(1)STL sort231518O(logn)可以看出STL sort在各类数据下表现最优插入排序对有序数据有惊人表现冒泡和选择排序只适合小规模数据在实际竞赛中建议n≤1e3任何算法都可1e3n≤1e6必须用O(nlogn)算法n1e6考虑基数排序等线性算法6. 常见错误与调试技巧新手在解决这类问题时容易遇到以下陷阱数组越界题目说n≤500但数组应稍微开大些如505边界条件当没有奇数时程序应能正确处理稳定性问题如果要求稳定排序不能直接用普通快排输出格式最后一个数后面不能有多余逗号调试时可以打印中间变量在排序前后输出数组内容使用小数据测试如全偶数、全奇数、单个元素等情况利用assert检查数组是否有序for(int i1;ian;i) assert(a[i]a[i1]);7. 扩展思考与练习题理解了本题后可以尝试以下变种题目偶数降序排列OpenJudge 1.10.03按数位和排序NOIP2007 提高组多关键字排序如先奇偶后大小推荐练习平台OpenJudge搜索排序相关题目CodeforcesProblemSet标签sortings洛谷官方题单《排序算法入门》对于想深入理解排序算法的同学建议阅读《算法导论》第2章和《编程珠玑》第11章里面有许多发人深省的见解。比如当Knuth被问到为什么没有在TAOCP中详细讨论冒泡排序时他回答说因为它在实践中没什么用除了作为错误排序算法的例子。